AT_ddcc2020_final_c Smaller-Suffix-Free Sequences

数列 $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$。

输入以如下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出共 $N$ 行。 第 $i$ 行输出 $(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)$ ## 样例解释 1 从 $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 连续子序列。 由 ChatGPT 4.1 翻译