/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
ビル 1, ビル 2, \ldots, ビル N の N 棟のビルがこの順で一列に並んでいます。ビル i\ (1\leq i\leq N) の高さは H_i です。
各 i=1,2,\ldots,N について、次を満たす整数 j\ (i\lt j\leq N) の個数を求めてください。
- ビル i とビル j の間にビル j より高いビルが存在しない。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq H_i\leq N
- H_i\neq H_j\ (i\neq j)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
各 i=1,2,\ldots,N に対して条件を満たす j の個数を c_i としたとき、c_1,c_2,\ldots,c_N をこの順で空白区切りで出力せよ。
入力例 1
5 2 1 4 3 5
出力例 1
3 2 2 1 0
i=1 について、条件を満たす j は 2,3,5 の 3 つです。（ビル 1 とビル 4 の間にはビル 4 より高いビル 3 が存在するため、j=4 は条件を満たしません。）よって、出力の 1 つ目は 3 になります。
入力例 2
4 1 2 3 4
出力例 2
3 2 1 0
入力例 3
10 1 9 6 5 2 7 10 4 8 3
出力例 3
2 3 3 3 2 1 2 1 1 0
Score : 400 points
Problem Statement
There are N buildings, Building 1, Building 2, \ldots, Building N, arranged in a line in this order. The height of Building i (1 \leq i \leq N) is H_i.
For each i = 1, 2, \ldots, N, find the number of integers j (i < j \leq N) satisfying the following condition:
- There is no building taller than Building j between Buildings i and j.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq N
- H_i\neq H_j\ (i\neq j)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
For each i = 1, 2, \ldots, N, let c_i be the number of j satisfying the condition. Print c_1, c_2, \ldots, c_N in order, separated by spaces.
Sample Input 1
5 2 1 4 3 5
Sample Output 1
3 2 2 1 0
For i=1, the integers j satisfying the condition are 2, 3, and 5: there are three. (Between Buildings 1 and 4, there is a building taller than Building 4, which is Building 3, so j=4 does not satisfy the condition.) Therefore, the first number in the output is 3.
Sample Input 2
4 1 2 3 4
Sample Output 2
3 2 1 0
Sample Input 3
10 1 9 6 5 2 7 10 4 8 3
Sample Output 3
2 3 3 3 2 1 2 1 1 0