题目描述

译自 JOI 2023 Final T1「碁石ならべ 2 / Stone Arranging 2」

JOI 君有 $N$ 个石子。石子从 $1$ 到 $N$ 编号。每个石子的颜色用一个 $1$ 到 $10^9$ 之间的整数表示（包括两端）。最初，第 $i\ (1\le i\le N)$ 颗石子的颜色是 $A_i$。

现在开始，JOI 君会进行 $N$ 次操作。他会把这些石子在桌子上排成一排。第 $i\ (1\le i\le N)$ 次操作按如下方式进行：

1. JOI 君会把石子 $i$ 放在石子 $i-1$ 的右边，并与其相邻。然而，当 $i=1$ 时，JOI 君会把石子 $1$ 放在桌子上。
2. 如果在石子 $1,2,\ldots,i-1$ 中，存在一个石子满足这个石子的颜色和第 $i$ 个石子相同，令 $j$ 为这样的石子中下标最大的，然后 JOI 君会把石子 $j+1,j+2,\ldots,i-1$ 都涂成 $A_i$ 颜色。

为了确认操作是否正确进行，JOI 君想提前知道在所有操作都进行之后，石子的颜色是什么。

给出这些石子的信息，写一个程序确定在 $N$ 次操作之后每个石子的颜色。

输入格式

第一行一个整数 $N$，表示石子个数。

接下来 $N$ 行，每行一个整数 $A_i$，表示每个石子的颜色。

输出格式

输出 $N$ 个整数，第 $i\ (1\le i\le N)$ 行表示 $N$ 次操作之后第 $i$ 个石子的颜色。

6
1
2
1
2
3
2

1
1
1
2
2
2

这些操作按下表所示过程进行。

最后，石子 $1,2,3,4,5,6$ 的颜色会分别变成 $1,1,1,2,2,2$。

这组样例满足子任务 $1,3$ 的限制。

10
1
1
2
2
1
2
2
1
1
2

1
1
1
1
1
1
1
1
1
2

这组样例满足所有子任务的限制。

数据范围与提示

对于全部数据，满足：

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

详细附加限制及分值如下表所示。