Rome
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 2.0 seconds
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 ith watchtower was built on the ith day.
The watchtowers often differed in height. The ith 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 ith of these representing h_i.
Output
You should output N lines. The ith of these should contain the amount of unsafe watchtowers after the ith 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.

Sample Input 1
5 2 4 4 2 2
Sample Output 1
1 2 1 2 1