K - Otemae Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

正整数 N と、 (1,2,\dots,N) の並べ替え A=(A_1,A_2,\dots,A_N) が与えられます。各 i=1,2,\dots,N に対して、以下の値を求めてください。

  • 1 \leq j < i かつ A_j > A_i を満たす整数 j が存在するならば、そのような j の最大値。存在しなければ -1。

制約

  • 1 \leq N \leq 5 \times 10^5
  • A は (1,2,\dots,N) の並べ替え

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

i=1,2,\dots,N に対する答えをこの順で空白区切りで 1 行に出力せよ。

入力例 1

4
3 1 4 2

出力例 1

-1 1 -1 3
  • i=1: 条件を満たす j は存在しないので、答えは -1 です。
  • i=2: j=1 が条件を満たすので、答えは 1 です。
  • i=3: 条件を満たす j は存在しないので、答えは -1 です。
  • i=4: j=1,3 が条件を満たします。そのうち、大きい方の 3 が答えです。

入力例 2

7
3 7 2 1 6 5 4

出力例 2

-1 -1 2 3 2 5 6

Problem Statement

You are given a positive integer N and a permutation A=(A_1,A_2,\dots,A_N) of (1,2,\dots,N). Find the following value for each i=1,2,\dots,N:

  • the maximum integer j such that 1 \leq j < i and A_j > A_i if such an integer exists, or -1 otherwise.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • A is a permutation of (1,2,\dots,N).

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answers for i=1,2,\dots,N in this order, with spaces in between.

Sample Input 1

4
3 1 4 2

Sample Output 1

-1 1 -1 3
  • i=1: No j satisfies the condition, so the answer is -1.
  • i=2: j=1 satisfies the condition, so the answer is 1.
  • i=3: No j satisfies the condition, so the answer is -1.
  • i=4: j=1,3 satisfy the condition, so the answer is 3, the larger of them.

Sample Input 2

7
3 7 2 1 6 5 4

Sample Output 2

-1 -1 2 3 2 5 6