问题文

一个序列 $T = (T_1, \ldots, T_L)$ 被称为是 smaller-suffix-free 的，如果对于所有 $i = 2, 3, \ldots, L$，序列 $(T_i, T_{i+1}, \ldots, T_L)$ 按字典序比 $T$ 大。例如，$(5)$ 和 $(1, 1, 2, 3)$ 是 smaller-suffix-free 的，而 $(3, 2, 1)$ 和 $(2, 2)$ 不是。

给定一个长度为 $N$ 的序列 $A = (A_1, \ldots, A_N)$。请找到对于每个 $i = 1, \ldots, N$，使得 $(A_i, A_{i+1}, \ldots, A_j)$ 是 smaller-suffix-free 的最大的 $j$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$ （$1 \leq i \leq N$）

输入

输入从标准输入中按以下格式给出。

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

输出

输出包含 $N$ 行。

第 $i$ 行输出使得 $(A_i, A_{i+1}, \ldots, A_j)$ 是 smaller-suffix-free 的最大的 $j$。

示例 1

6
3 2 1 1 2 3

示例 1 输出

1
2
6
6
6
6

以 $A_1$ 开头的最长的 smaller-suffix-free 子序列是 $(A_1) = (3)$。因此在第 1 行输出 $1$。

同样地，$(A_2), (A_3, A_4, A_5, A_6), (A_4, A_5, A_6), (A_5, A_6), (A_6)$ 分别是以 $A_i$（其中 $2 \leq i \leq 6$）开头的最长的 smaller-suffix-free 子序列。

示例 2

3
10 10 10

示例 2 输出

1
2
3