← 返回题目列表

Codeforces · 900/C

C. 删除多余的一个

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

给定一个长度为 n 的排列 p。从排列中删除一个元素以使记录数尽可能多。

我们提醒一下,在数字 a1, a2, ..., ak 序列中,如果对于每个整数 j (1 ≤ j < i) 满足以下条件,则元素 ai 是一条记录:aj < ai。

输入

第一行包含唯一的整数 n (1 ≤ n ≤ 105) — 排列的长度。

第二行包含 n 个整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — 排列。所有整数都是不同的。

输出

打印唯一的整数 - 应该删除以使记录数达到最大可能的元素。如果有多个这样的元素,则打印最小的一个。

示例

输入 #1

1
1

输出 #1

1

输入 #2

5
5 1 2 3 4

输出 #2

5

注意

在第一个示例中,可以删除唯一的元素。