C - 退場する選手と順位表 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は N 人の選手が参加するマラソン大会の運営をしています。選手には 1 から N までの番号が付けられており、選手 i（i = 1, 2, \ldots, N）には「スタミナ値」 L_i が定められています。スタミナ値は 1 から N の順列、すなわち 1 以上 N 以下の整数がすべて異なる値として割り当てられています。

大会では、 N 人の選手が左から右へ一列に並んでスタートします。最初、選手 i は左から i 番目の位置にいます。つまり、選手の番号と初期位置は一致しています。

レースが始まると、選手たちはスタミナ値が小さい順に一人ずつリタイアしていきます。つまり、最初にスタミナ値 1 の選手がリタイアし、次にスタミナ値 2 の選手がリタイアし、……と続き、最後にスタミナ値 N の選手がリタイアします。

選手がリタイアすると、その選手は列から抜けます。残った選手たちは相対的な順序を保ったまま隙間なく詰められ、再び左から連続して並んだ状態になります。

高橋君は記録係として、各選手がリタイアする直前の時点で、その選手が残っている選手たちの中で左から何番目にいるかを記録したいと考えています。ここで「リタイア直前」とは、その選手自身もまだ列に残っている状態を指します。

スタミナ値 k の選手がリタイアする直前に、その選手自身を含む残りの選手の中で左から何番目にいたかを、 k = 1, 2, \ldots, N の順に求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq N
  • L_1, L_2, \ldots, L_N は 1 から N の順列である
  • 入力はすべて整数である

入力

N
L_1 L_2 \ldots L_N
  • 1 行目には、選手の人数を表す整数 N が与えられる。
  • 2 行目には、選手 i（i = 1, 2, \ldots, N）のスタミナ値を表す整数 L_i が N 個、スペース区切りで与えられる。

出力

N 行出力せよ。 k 行目（ k = 1, 2, \ldots, N ）には、スタミナ値 k の選手がリタイアする直前に、その選手自身を含む残りの選手の中で左から何番目にいたかを表す整数を出力せよ。

入力例 1

5
3 1 4 5 2

出力例 1

2
4
1
1
1

入力例 2

4
4 3 2 1

出力例 2

4
3
2
1

入力例 3

10
5 3 8 1 10 2 7 9 4 6

出力例 3

4
5
2
6
1
5
3
1
2
1

入力例 4

20
12 5 18 3 14 9 20 1 16 7 11 19 6 2 17 10 4 15 8 13

出力例 4

8
13
4
14
2
10
7
12
4
9
6
1
8
2
6
3
4
1
2
1

入力例 5

1
1

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is organizing a marathon with N participants. The players are numbered from 1 to N, and each player i (i = 1, 2, \ldots, N) has a "stamina value" L_i. The stamina values are a permutation of 1 through N, meaning they are distinct integers between 1 and N inclusive.

In the race, the N players line up in a single row from left to right at the start. Initially, player i is at the i-th position from the left. In other words, each player's number matches their initial position.

Once the race begins, players retire one by one in increasing order of their stamina values. That is, the player with stamina value 1 retires first, then the player with stamina value 2, and so on, until finally the player with stamina value N retires.

When a player retires, they leave the row. The remaining players maintain their relative order and close any gaps, forming a contiguous row from the left again.

As the record keeper, Takahashi wants to record, just before each player retires, what position from the left that player holds among the remaining players. Here, "just before retiring" means the player themselves is still in the row at that point.

For k = 1, 2, \ldots, N in order, determine the position from the left of the player with stamina value k among the remaining players (including themselves) just before that player retires.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_i \leq N
  • L_1, L_2, \ldots, L_N is a permutation of 1 through N
  • All input values are integers

Input

N
L_1 L_2 \ldots L_N
  • The first line contains an integer N, the number of players.
  • The second line contains N integers L_i separated by spaces, representing the stamina value of player i (i = 1, 2, \ldots, N).

Output

Print N lines. The k-th line (k = 1, 2, \ldots, N) should contain an integer representing the position from the left of the player with stamina value k among the remaining players (including themselves) just before that player retires.

Sample Input 1

5
3 1 4 5 2

Sample Output 1

2
4
1
1
1

Sample Input 2

4
4 3 2 1

Sample Output 2

4
3
2
1

Sample Input 3

10
5 3 8 1 10 2 7 9 4 6

Sample Output 3

4
5
2
6
1
5
3
1
2
1

Sample Input 4

20
12 5 18 3 14 9 20 1 16 7 11 19 6 2 17 10 4 15 8 13

Sample Output 4

8
13
4
14
2
10
7
12
4
9
6
1
8
2
6
3
4
1
2
1

Sample Input 5

1
1

Sample Output 5

1