{"problem":{"name":"C. Remove Extra One","description":{"content":"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_ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF900C"},"statements":[{"statement_type":"Markdown","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_.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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.\n\n[samples]\n\n## Note\n\nIn the first example the only element can be removed.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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在第一个例子中，只能删除唯一的一个元素。\n\n## Input\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——排列的长度。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 ≤ p_i ≤ n$）——排列。所有整数互不相同。\n\n## Output\n\n请输出一个整数——应删除的元素，使得记录个数最大化。如果有多个这样的元素，请输出最小的那个。\n\n[samples]\n\n## Note\n\n在第一个例子中，只能删除唯一的一个元素。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF900C","tags":["brute force","data structures","math"],"sample_group":[["1\n1","1"],["5\n5 1 2 3 4","5"]],"created_at":"2026-03-03 11:00:39"}}