MWC '15 #2 P2: Towering Towers

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.4s
Java 0.7s
Python 0.7s
Memory limit: 256M

Problem type

icicreampoph has N towers, all arranged in a straight line, with each tower having a given height H_i. When he is in a given tower, he can only see the towers which are to the left of his tower. Specifically, he can only see all consecutive towers just before his tower which do not have a greater height than his current tower. If there is a tower which is taller than the tower icicreampoph is in, he will see the tower blocking his view, but nothing past it.

icicreampoph wants to know how many towers he can see from each tower, but being lazy and not wanting to move from tower to tower, he asks you to do it for him!

Input Specification

The first line will contain an integer N (1 \leq N \leq 10^6), specifying the number of towers that icicreampoph has. The second line will contain N integers H_i (1 \leq H_i \leq 10^6), each representing the height of the i^{th} tower.

Output Specification

Output should consist of one line, with N space separated integers, the i^{th} number representing the number of towers icicreampoph can see when in the i^{th} tower.

Sample Input

7 4 5 4 4

Sample Output

0 1 2 1 2

Explanation of Sample Output

Arrows represent the view from each tower.


There are no comments at the moment.