LCC '18 Contest 2 J5 - Tall People 2

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

You are the teacher for a class of N students, and you have decided to do an activity with them. The N students are lined up in a single file line, facing forward. Each student i has a height h_i, and can see all students j that are in front of them (1 \le j < i), up to the first student k who has a height h_k \ge h_i. Each student reports the number of students they can see. That is, they report i-k. Note the first student can see 0 students, because there are no students in front of them.

However, you notice that some students are not reporting the actual number of students they can see. Knowing each student's height, and wanting to punish the students who are reporting fake numbers. you want to know how many students the i^{th} student can see.

Input Specification

The first line contains the integer, N (1 \le N \le 10^5), the number of students in the class.

The second line contains the heights of each student, h_1, h_2, \ldots, h_N (1 \le h_i \le 10^6).

Output Specification

On the first and only line, print N integers separated by spaces, the i^{th} integer being the number of students the i^{th} student can see.


Subtask 1 [30%]

N \le 100

Subtask 2 [70%]

No further constraints.

Sample Input

3 8 1000000 1000000 1 9 3 10

Sample Output

0 1 2 1 1 2 1 4


There are no comments at the moment.