题目描述

译自 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$ 个石子的颜色。

样例 1

输入

6
1
2
1
2
3
2

输出

1
1
1
2
2
2

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

操作	桌子上石子的颜色	解释
1		石子 1 被放在桌子上
2	1,2	石子 2 紧挨着石子 1 并放在其右边
3	1,2,1	石子 3 紧挨着石子 2 并放在其右边
	1,1,1	石子 2 被涂成颜色 1
4	1,1,1,2	石子 4 紧挨着石子 3 并放在其右边
5	1,1,1,2,3	石子 5 紧挨着石子 4 并放在其右边
6	1,1,1,2,3,2	石子 6 紧挨着石子 5 并放在其右边
	1,1,1,2,2,2	石子 5 被涂成颜色 2

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

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

样例 2

输入

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)$

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

子任务编号	附加限制	分值
1	$N\le 2\,000$	$25$
2	$A_i\le 2\ (1\le i\le N)$	$35$
3	无附加限制	$40$