← 返回题目列表

AtCoder · ddcc2020_final_c

C. 较小的无后缀序列

中文机器翻译题面 查看原题

配点 : 800 点

問題文

数列 T = (T_1, \ldots, T_L) 没有较小的后缀。 i = 2, 3, \ldots, L 对于一切,顺序 (T_i, T_{i+1}, \ldots, T_L) 是 按字典顺序 这意味着大于 T 。 例如 (5) 呀 (1, 1, 2, 3) 是较小的无后缀并且(3, 2, 1) 呀 (2, 2) 不是无较小后缀的。

长度 N 序列 给出了 A = (A_1, \ldots, A_N) 。 每个 关于 i = 1, \ldots, N , 最大的使得(A_i, A_{i+1}, \ldots, A_j) 更小,无后缀 以 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) 更小,无后缀 以 j 。


入力例 1

6
3 2 1 1 2 3

出力例 1

1
2
6
6
6
6

A_1 开头的无较小后缀的最长连续子序列是 (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) 开头的无较小后缀的最长连续子序列。


入力例 2

3
10 10 10

出力例 2

1
2
3