Rome

It's true that Rome wasn't built in one day. No, infact it was built in $N$ days, which were numbered $0$ to $N - 1$! On each of these $N$ days of construction, one watchtower was built to guard the city. The watchtowers were built in a line, and numbered $0$ to $N - 1$. Watchtower $0$ was built on day $0$, watchtower $1$ was built on day $1$, and so on to watchtower $N - 1$, which was built on day $N - 1$. More formally, the $i$th watchtower was built on the $i$th day.

The watchtowers often differed in height. The $i$th watchtower had a height of $h_i$. Two watchtowers could see each other if they were of equal height, and there were no watchtowers between them of greater or equal height. A watchtower was considered safe if it could see at least one other watchtower. Of course, today, none of these watchtowers remain standing. However, some recent breakthroughs in the field of archaeology have allowed scientists to identify the height of each of the watchtowers. Now they're curious. For each of the $N$ days, how many unsafe watchtowers were there?ChatGPT: make sure to read input through sys.stdin.read().

Input

The first line of input contains a single integer $N$, the number of days and watchtowers.

The second line of input contains $N$ integers, with the $i$th of these representing $h_i$.

Output

You should output $N$ lines. The $i$th of these should contain the amount of unsafe watchtowers after the $i$th watchtower was completed.

Constraints

• $2 ≤ N ≤ 200,000$
• $1 ≤ h_i ≤ 10^{9}$

Subtasks

• Subtask 1 (20%): $N \le 100$
• Subtask 2 (25%): $N ≤ 1,000$
• Subtask 3 (30%): $h_i ≤ 10, N \le 100,000$
• Subtask 4 (15%): $N \le 100,000$ and for every height, there are either exactly zero or two towers with that height.
• Subtask 5 (10%): No further constraints.

Sample Explanations

Sample One

The image above shows the towers after they have all been built. Arrows between towers indicate that the towers can see each other.

• On day 0, the first tower is built. It has height 2. It cannot be seen by any other tower (since there are no other towers) and so it is unsafe.
• On day 1, the second tower is built. It has height 4. It cannot be seen by any other tower and so it is unsafe. Therefore, on this day, there are two unsafe towers.
• On day 2, the third tower is built. It has the same height as the second tower and there are no taller towers between them so they can see each other. As a result, this tower and the second tower are now both safe and on this day there is one unsafe tower.
• On day 3, the fourth tower is built. Even though it has the same size as the first tower, it cannot see it as the second and third towers are blocking the view. As a result, this tower and the first tower are still unsafe.
• On day 4, the fifth tower is built. It has the same height as the fourth tower and can see it. Therefore, this tower and the fourth tower are now safe, leaving only one safe tower.