← 返回题目列表

Codeforces · 250/C

C. 影评人

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

A film festival is coming up in the city N. The festival will last for exactly n days and each day will have a premiere of exactly one film.每部电影都有一个类型——从 1 到 k 的整数。

在第 i 天,电影节将放映一部 ai 类型的电影。我们知道,k 种类型的电影在电影节节目中至少出现一次。换句话说,从 1 到 k 的每个整数在序列 a1, a2, ..., an 中至少出现一次。

Valentine is a movie critic.他想观看一些电影节的电影,然后在他的网站上描述他的印象。

与任何有创造力的人一样,瓦伦丁非常容易受到影响。在观看某种类型的电影后,瓦伦丁形成了他一直保留的情绪,直到他观看下一部电影。如果下一部电影的类型相同,也不会改变瓦伦丁的心情。如果流派不同,瓦伦丁的心情会根据新流派而变化,瓦伦丁会有压力。

Valentine 无法观看所有 n 部电影,因此他决定从观看列表中排除其中一种类型的电影。换句话说,Valentine 将恰好选择 k 个类型中的一种,并跳过该类型的所有电影。 He is sure to visit other movies.

Valentine想要选择这样的类型x(1≤x≤k),使得电影后压力的总数(在排除类型x的所有电影之后)最少。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ k ≤ n ≤ 105),其中 n 是电影数量,k 是流派数量。

输入的第二行包含 n 个正整数 a1, a2, ..., an (1 ≤ ai ≤ k) 的序列,其中 ai 是第 i 部电影的类型。保证从 1 到 k 的每个数字在此序列中至少出现一次。

输出

打印单个数字 — 排除的电影的类型编号(从 1 到 k)。如果有多个答案,则打印出数量最少的类型。

示例

输入 #1

10 3
1 1 2 3 2 3 3 1 1 3

输出 #1

3

输入 #2

7 3
3 1 3 2 3 1 2

输出 #2

1

注意

在第一个样本中,如果我们排除第 1 类型的电影,则类型 2, 3, 2, 3, 3, 3 保留,即 3 个重音;如果我们排除第2类型的电影,则保留类型1, 1, 3, 3, 3, 1, 1, 3,即3重音;如果我们排除第三种类型的电影,则类型 1, 1, 2, 2, 1, 1 仍然存在,即 2 重音。

在第二个样本中,无论 Valentine 排除什么类型,他都会有 3 个压力。