Border Watchtower Downrange Peak

EasyArraySuffix maxRunning maxScanning2 sample tests6 hidden tests

A border-security agency maintains a straight line of n watchtowers along a stretch of frontier fence, numbered 0 (westernmost) through n-1 (easternmost). Tower i currently has a recorded height, height[i]. For an upcoming line-of-sight audit, the agency wants each tower's recorded value replaced by the tallest height among all towers strictly to its east -- that is, among towers with a larger index. The easternmost tower has no tower to its east, so its updated value must become -1.

Input format

Line 1: a single integer n.
Line 2: n space-separated integers, height[0] .. height[n-1].

Output format

Print n space-separated integers: the updated heights, in tower order.

Constraints

1 <= n <= 10^5
1 <= height[i] <= 10^9

Examples

Example 1

Input

5
5 4 3 2 1

Expected

4 3 2 1 -1

Explanation

Heights are strictly decreasing: 5 4 3 2 1. For tower 0 the tallest tower east of it is height 4 (tower 1); for tower 1 it's height 3; for tower 2 it's height 2; for tower 3 it's height 1 (tower 4); tower 4 is the easternmost tower and becomes -1. Result: 4 3 2 1 -1.

Example 2

Input

4
2 7 3 7

Expected

7 7 7 -1

Explanation

Heights are 2 7 3 7. East of tower 0 the towers are [7, 3, 7], tallest is 7. East of tower 1 the towers are [3, 7], tallest is 7. East of tower 2 the only tower is [7], so 7. Tower 3 is the easternmost and becomes -1. Result: 7 7 7 -1.

Ready to solve this?