{"raw_statement":[{"iden":"statement","content":"You are given a permutation _p_ of length _n_. Remove one element from permutation to make the number of records the maximum possible.\n\nWe 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_ < _i_) the following holds: _a__j_ < _a__i_."},{"iden":"input","content":"The first line contains the only integer _n_ (1 ≤ _n_ ≤ 105) — the length of the permutation.\n\nThe second line contains _n_ integers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — the permutation. All the integers are distinct."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n1\n1\n\nOutput\n\n1\n\nInput\n\n5\n5 1 2 3 4\n\nOutput\n\n5"},{"iden":"note","content":"In the first example the only element can be removed."}],"translated_statement":[{"iden":"statement","content":"你被给定一个长度为 $n$ 的排列 $p$。请从该排列中删除一个元素，使得记录的个数最大化。\n\n我们提醒你，在一个数列 $[a_1, a_2, ..., a_k]$ 中，元素 $a_i$ 是一个 _记录_，当且仅当对每个整数 $j$（$1 ≤ j < i$）都有：$a_j < a_i$。\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——排列的长度。\n\n第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 ≤ p_i ≤ n$）——排列。所有整数互不相同。\n\n请输出一个整数——应删除的元素，使得记录个数最大化。如果有多个这样的元素，请输出最小的那个。\n\n在第一个例子中，只能删除唯一的一个元素。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——排列的长度。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 ≤ p_i ≤ n$）——排列。所有整数互不相同。"},{"iden":"output","content":"请输出一个整数——应删除的元素，使得记录个数最大化。如果有多个这样的元素，请输出最小的那个。"},{"iden":"examples","content":"输入11输出1输入55 1 2 3 4输出5"},{"iden":"note","content":"在第一个例子中，只能删除唯一的一个元素。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^5 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \n\nFor a sequence $ A = (a_1, a_2, \\dots, a_k) $, define the set of records:  \n$$\n\\text{Records}(A) = \\left\\{ a_i \\,\\middle|\\, \\forall j < i,\\, a_j < a_i \\right\\}\n$$  \nLet $ r(A) = |\\text{Records}(A)| $ denote the number of records in $ A $.  \n\nFor each $ i \\in \\{1, \\dots, n\\} $, define $ P^{(i)} $ as the sequence obtained by removing $ p_i $ from $ P $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ p_i \\in \\{1, 2, \\dots, n\\} $, all distinct  \n\n**Objective**  \nFind the smallest $ p_i $ such that:  \n$$\nr(P^{(i)}) = \\max_{1 \\leq j \\leq n} r(P^{(j)})\n$$","simple_statement":null,"has_page_source":false}