← 返回题目列表

Codeforces · 886/B

B. 弗拉德和咖啡馆

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

Vlad非常喜欢在咖啡馆吃饭。他一生中去过咖啡馆n次。不幸的是,弗拉德开始觉得他上次的访问并没有什么不同。为了解决这个问题,弗拉德进行了一项小型研究。

首先,Vlad 为所有咖啡馆分配了单独的索引。然后,他按照访问的顺序写下了他连续访问过的咖啡馆的索引。现在,弗拉德想要找到这样一家咖啡馆,他最后一次访问该咖啡馆是在他最后一次访问其他所有咖啡馆之前。也就是说,他想尽可能找到一家自己很久没有去过的咖啡馆。帮助弗拉德找到那家咖啡馆。

输入

第一行有一个整数 n (1 ≤ n ≤ 2·105) — Vlad 编写的咖啡馆索引数量。

在第二行中,写入了 n 个数字 a1, a2, ..., an (0 ≤ ai ≤ 2·105) — 按 Vlad 访问顺序排列的咖啡馆索引。弗拉德可以不止一次地去一些咖啡馆。请注意,在计数时,可以省略一些索引。

输出

打印一个整数——Vlad 尽可能长时间没有去过的咖啡馆的索引。

示例

输入 #1

5
1 3 2 1 2

输出 #1

3

输入 #2

6
2 1 2 2 4 1

输出 #2

2

注意

在第一次测试中,有 3 个咖啡馆,最后一次访问索引为 1 和 2 的咖啡馆是在上次访问索引为 3 的咖啡馆之后;所以这家咖啡馆就是答案。

在第二个测试用例中,也有三个咖啡馆,但索引分别为 1、2 和 4。在上次访问索引为 2 的咖啡馆之后,还访问了索引为 1 和 4 的咖啡馆,因此答案为 2。请注意,Vlad 在计算咖啡馆时可以省略一些数字。