C. Remove Extra One

Codeforces

IDCF900C

Time2000ms

Memory256MB

Difficulty—

brute forcedata structuresmath

English · Original

Chinese · Translation

Formal · Original

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_ < _i_) the following holds: _a__j_ < _a__i_. ## Input The first line contains the only integer _n_ (1 ≤ _n_ ≤ 105) — 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. ## Output 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. [samples] ## Note In the first example the only element can be removed.

你被给定一个长度为 $n$ 的排列 $p$。请从该排列中删除一个元素，使得记录的个数最大化。我们提醒你，在一个数列 $[a_1, a_2, ..., a_k]$ 中，元素 $a_i$ 是一个 _记录_，当且仅当对每个整数 $j$（$1 ≤ j < i$）都有：$a_j < a_i$。第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——排列的长度。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 ≤ p_i ≤ n$）——排列。所有整数互不相同。请输出一个整数——应删除的元素，使得记录个数最大化。如果有多个这样的元素，请输出最小的那个。在第一个例子中，只能删除唯一的一个元素。 ## Input 第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——排列的长度。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1 ≤ p_i ≤ n$）——排列。所有整数互不相同。 ## Output 请输出一个整数——应删除的元素，使得记录个数最大化。如果有多个这样的元素，请输出最小的那个。 [samples] ## Note 在第一个例子中，只能删除唯一的一个元素。

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^5 $. Let $ P = (p_1, p_2, \dots, p_n) $ be a permutation of $ \{1, 2, \dots, n\} $. For a sequence $ A = (a_1, a_2, \dots, a_k) $, define the set of records: $$ \text{Records}(A) = \left\{ a_i \,\middle|\, \forall j < i,\, a_j < a_i \right\} $$ Let $ r(A) = |\text{Records}(A)| $ denote the number of records in $ A $. For each $ i \in \{1, \dots, n\} $, define $ P^{(i)} $ as the sequence obtained by removing $ p_i $ from $ P $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ p_i \in \{1, 2, \dots, n\} $, all distinct **Objective** Find the smallest $ p_i $ such that: $$ r(P^{(i)}) = \max_{1 \leq j \leq n} r(P^{(j)}) $$

Samples

Input #1

1
1

Output #1

Input #2

5
5 1 2 3 4

Output #2

API Response (JSON)

{
  "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_ ...",
      "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$ 个整数 $...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments