Remove Extra One

题意翻译

给一个长度为n的排列p，找一个元素，使得从排列中取出这个元素以后排列的“records”最多。 一个"record"是一个元素$a_i$满足：对于每个正整数 $1\le j <i$ , $a_i > a_j$.

题目描述

You are given a permutation $ p $ of length $ n $ . Remove one element from permutation to make the number of records the maximum possible. We remind that in a sequence of numbers $ a_{1},a_{2},...,a_{k} $ the element $ a_{i} $ is a record if for every integer $ j $ ( $ 1<=j&lt;i $ ) the following holds: $ a_{j}&lt;a_{i} $ .

输入输出格式

输入格式

The first line contains the only integer $ n $ ( $ 1<=n<=10^{5} $ ) — the length of the permutation. The second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ ( $ 1<=p_{i}<=n $ ) — the permutation. All the integers are distinct.

输出格式

Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

输入输出样例

输入样例 #1

1
1

输出样例 #1

1

输入样例 #2

5
5 1 2 3 4

输出样例 #2

5

说明

In the first example the only element can be removed.

题意翻译

给一个长度为n的排列p，找一个元素，使得从排列中取出这个元素以后排列的“records”最多。 一个"record"是一个元素$a_i$满足：对于每个正整数 $1\le j <i$ , $a_i > a_j$.