D. Multicolored Cars

Codeforces

IDCF818D

Time2000ms

Memory256MB

Difficulty—

data structuresimplementation

English · Original

Chinese · Translation

Formal · Original

Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another. The game rules are like this. Firstly Alice chooses some color _A_, then Bob chooses some color _B_ (_A_ ≠ _B_). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after _i_\-th car _cnt__A_(_i_) and _cnt__B_(_i_). * If _cnt__A_(_i_) > _cnt__B_(_i_) for every _i_ then the winner is Alice. * If _cnt__B_(_i_) ≥ _cnt__A_(_i_) for every _i_ then the winner is Bob. * Otherwise it's a draw. Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color _A_ and Bob now wants to choose such color _B_ that he will win the game (draw is not a win). Help him find this color. If there are multiple solutions, print any of them. If there is no such color then print _\-1_. ## Input The first line contains two integer numbers _n_ and _A_ (1 ≤ _n_ ≤ 105, 1 ≤ _A_ ≤ 106) – number of cars and the color chosen by Alice. The second line contains _n_ integer numbers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 106) — colors of the cars that Alice and Bob will encounter in the order of their appearance. ## Output Output such color _B_ (1 ≤ _B_ ≤ 106) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print _\-1_. It is guaranteed that if there exists any solution then there exists solution with (1 ≤ _B_ ≤ 106). [samples] ## Note Let's consider availability of colors in the first example: * _cnt_2(_i_) ≥ _cnt_1(_i_) for every _i_, and color 2 can be the answer. * _cnt_4(2) < _cnt_1(2), so color 4 isn't the winning one for Bob. * All the other colors also have _cnt__j_(2) < _cnt_1(2), thus they are not available. In the third example every color is acceptable except for 10.

Alice 和 Bob 在一次漫长的车程中感到非常无聊，于是决定玩一个游戏。从车窗望去，他们可以看到不同颜色的汽车依次驶过。游戏规则如下：首先 Alice 选择一种颜色 #cf_span[A]，然后 Bob 选择另一种颜色 #cf_span[B]（#cf_span[A ≠ B]）。每经过一辆车，他们都会更新自己所选颜色的汽车数量。定义经过第 #cf_span[i] 辆车后，Alice 和 Bob 所选颜色的计数分别为 #cf_span[cntA(i)] 和 #cf_span[cntB(i)]。 Bob 知道他们将遇到的所有汽车的颜色及其出现顺序。Alice 已经选择了她的颜色 #cf_span[A]，现在 Bob 希望选择一个颜色 #cf_span[B]，使得他能赢得游戏（平局不算赢）。请帮他找到这样一个颜色。如果有多个解，请输出任意一个。如果没有这样的颜色，请输出 _-1_。第一行包含两个整数 #cf_span[n] 和 #cf_span[A]（#cf_span[1 ≤ n ≤ 105, 1 ≤ A ≤ 106]）——汽车总数和 Alice 选择的颜色。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 106]）——表示 Alice 和 Bob 按出现顺序将遇到的汽车颜色。请输出一个颜色 #cf_span[B]（#cf_span[1 ≤ B ≤ 106]），使得如果 Bob 选择它，他就能赢得游戏。如果有多个解，输出任意一个；如果没有这样的颜色，则输出 _-1_。题目保证：如果存在解，则一定存在一个满足 (#cf_span[1 ≤ B ≤ 106]) 的解。让我们分析第一个例子中颜色的可用性：在第三个例子中，除了 #cf_span[10] 之外的所有颜色都是可接受的。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[A]（#cf_span[1 ≤ n ≤ 105, 1 ≤ A ≤ 106]）——汽车总数和 Alice 选择的颜色。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 106]）——表示 Alice 和 Bob 按出现顺序将遇到的汽车颜色。 ## Output 请输出一个颜色 #cf_span[B]（#cf_span[1 ≤ B ≤ 106]），使得如果 Bob 选择它，他就能赢得游戏。如果有多个解，输出任意一个；如果没有这样的颜色，则输出 _-1_。题目保证：如果存在解，则一定存在一个满足 (#cf_span[1 ≤ B ≤ 106]) 的解。 [samples] ## Note 让我们分析第一个例子中颜色的可用性：对每个 #cf_span[i]，都有 #cf_span[cnt2(i) ≥ cnt1(i)]，因此颜色 #cf_span[2] 可以作为答案。而 #cf_span[cnt4(2) < cnt1(2)]，所以颜色 #cf_span[4] 不是 Bob 的获胜选择。其他所有颜色也都有 #cf_span[cntj(2) < cnt1(2)]，因此均不可用。在第三个例子中，除了 #cf_span[10] 之外的所有颜色都是可接受的。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of cars. Let $ A \in \mathbb{Z}^+ $ be Alice’s chosen color. Let $ C = (c_1, c_2, \dots, c_n) $ be the sequence of car colors, where $ c_i \in \mathbb{Z}^+ $. For any color $ x \in \mathbb{Z}^+ $, define the cumulative count function: $$ \text{cnt}_x(i) = \left| \{ j \in \{1, \dots, i\} \mid c_j = x \} \right| $$ **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq A \leq 10^6 $ 3. $ 1 \leq c_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $ 4. $ B \neq A $, and $ B \in \{1, \dots, 10^6\} $ **Objective** Find a color $ B \neq A $ such that: $$ \text{cnt}_B(n) > \text{cnt}_A(n) $$ If multiple such $ B $ exist, output any. If none exists, output $-1$.

Samples

Input #1

4 1
2 1 4 2

Output #1

Input #2

5 2
2 2 4 5 3

Output #2

\-1

Input #3

3 10
1 2 3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Multicolored Cars",
    "description": {
      "content": "Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another. The game",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF818D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.\n\nThe game...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alice 和 Bob 在一次漫长的车程中感到非常无聊，于是决定玩一个游戏。从车窗望去，他们可以看到不同颜色的汽车依次驶过。\n\n游戏规则如下：首先 Alice 选择一种颜色 #cf_span[A]，然后 Bob 选择另一种颜色 #cf_span[B]（#cf_span[A ≠ B]）。每经过一辆车，他们都会更新自己所选颜色的汽车数量。定义经过第 #cf_span[i] 辆车后，Alice 和 Bo...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cars.  \nLet $ A \\in \\mathbb{Z}^+ $ be Alice’s chosen color.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be the sequence of car colors, where $ c_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments