Problem Description

A sequence $T = (T_1, \ldots, T_L)$ is called smaller-suffix-free if, for all $i = 2, 3, \ldots, L$, the sequence $(T_i, T_{i+1}, \ldots, T_L)$ is lexicographically greater than $ T $. For example, $ (5) $ and $ (1, 1, 2, 3) $ are smaller-suffix-free, while $ (3, 2, 1) $ and $ (2, 2) $ are not smaller-suffix-free.

Given a sequence $A = (A_1, \ldots, A_N)$ of length $ N $. For each $i = 1, \ldots, N$, find the maximum $ j $ such that $(A_i, A_{i+1}, \ldots, A_j)$ is smaller-suffix-free.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $

Output Format

The output consists of $ N $ lines.

On the $ i $-th line, output the maximum $ j $ such that $(A_i, A_{i+1}, \ldots, A_j)$ is smaller-suffix-free.

Sample Input and Output

Sample Input #1

6
3 2 1 1 2 3

Sample Output #1

1
2
6
6
6
6

Sample Input #2

3
10 10 10

Sample Output #2

1
2
3

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5\ (1 \leq i \leq N)$

Sample Explanation 1

The longest consecutive subsequence starting from $ A_1 $ that is smaller-suffix-free is $ (A_1) = (3) $. Therefore, output $ 1 $ on the first line. Similarly, $ (A_2), (A_3, A_4, A_5, A_6), (A_4, A_5, A_6), (A_5, A_6), (A_6) $ are the longest consecutive subsequences starting from $A_i\ (2 \leq i \leq 6)$ that are smaller-suffix-free.

见题面 Input 部分

见题面 Output 部分