← 返回题目列表

Codeforces · 818/D

D. 五彩汽车

中文机器翻译题面 查看原题

Alice 和 Bob 在长途汽车旅行中感到非常无聊,所以他们决定玩一个游戏。从窗户里他们可以看到不同颜色的汽车从他们身边驶过。汽车一辆接一辆地行驶。

游戏规则是这样的。首先Alice选择某种颜色A,然后Bob选择某种颜色B(A≠B)。每辆车行驶完后,他们都会更新经过他们的所选颜色的汽车数量。让我们在第 i 辆车 cntA(i) 和 cntB(i) 之后定义这个数字。

- 如果每个 i 的 cntA(i) > cntB(i) 则获胜者是 Alice。
- 如果对于每个 i 来说 cntB(i) ≥ cntA(i) 那么获胜者是 Bob。
- 否则就是平局。

鲍勃知道他们将遇到的汽车的所有颜色以及它们的出现顺序。 Alice 已经选择了她的颜色 A,而 Bob 现在想选择颜色 B,这样他就能赢得比赛(平局不是胜利)。帮他找到这种颜色。

如果有多个解决方案,请打印其中任何一个。如果没有这种颜色则打印-1。

输入

第一行包含两个整数 n 和 A (1 ≤ n ≤ 105, 1 ≤ A ≤ 106) – 汽车数量和 Alice 选择的颜色。

第二行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ 106) — Alice 和 Bob 将按照出现顺序遇到的汽车的颜色。

输出

输出这样的颜色 B (1 ≤ B ≤ 106),如果 Bob 选择它,那么他将赢得比赛。如果有多个解决方案,请打印其中任何一个。如果没有这种颜色则打印-1。

保证如果存在解则存在 (1 ≤ B ≤ 106) 的解。

示例

输入 #1

4 1
2 1 4 2

输出 #1

2

输入 #2

5 2
2 2 4 5 3

输出 #2

-1

输入 #3

3 10
1 2 3

输出 #3

4

注意

让我们考虑第一个示例中颜色的可用性:

- 对于每个 i,cnt2(i) ≥ cnt1(i),颜色 2 可以作为答案。
- cnt4(2) < cnt1(2),因此颜色 4 不是 Bob 的获胜颜色。
- 所有其他颜色也有 cntj(2) < cnt1(2),因此它们不可用。

在第三个示例中,除 10 之外的所有颜色都是可接受的。