Tower View

Interview

Time limit1.5sMemory limit1024 MB

Summary

For each building, count the buildings visible to its left and right, where a shorter or equal building is hidden behind a taller one, and report the nearest visible index.

Level: Medium7 of 10
Topics: Stack, Array, Implementation, Two pointers
Solved: No attempts yet

Problem

There are $N$ buildings of various heights on a straight line. From the roof of each building, you want to know how many sides of buildings are visible on either side.

For the $i$ -th building, buildings $i - 1$ , $i - 2$ , ..., $1$ are on the left, and buildings $i + 1$ , $i + 2$ , ..., $N$ are on the right. The distance between adjacent buildings is the same.

Suppose the current building has height $L$ . Only buildings with height greater than $L$ are visible.

In the direction you are looking, if a building of height at most $L$ lies behind a building of height $L$ , it is hidden and not visible.


Index	1	2	3	4	5	6	7	8
Height	3	7	1	6	3	5	1	7
Visible buildings	2	x	2, 4, 8	2, 8	2,4,6,8	2,4,8	2,4,6,8	x

Find which buildings are visible from each building.

Input

The first line gives the number of buildings $N$ .

The second line gives the heights of the $N$ buildings, separated by spaces.

Output

For each building $i(1 \le i \le N)$ , output the number of visible buildings.

If the number of visible buildings is at least 1, also output the smallest index among the visible buildings closest to building $i$ .

Constraints

$1 \le N \le 100,000$
$1 \le L \le 100,000$

Examples1

Example 1

Input

8
3 7 1 6 3 5 1 7

Expected output