← 返回题目列表

AtCoder · codefestival_2015_qualB_b

B. 分级

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

问题陈述

高桥先生正在批改学生的试卷。不幸的是,他忘记了某个问题的正确答案。

N 学生回答这个问题的整数介于 0 和 M,包括在内。他决定假设正确答案是整数 X 如果超过一半的学生回答 X.

您将获得以下问题的答案 N 同学提这个问题。如果他假设正确答案是某个整数 X,打印值 X。如果他无法假设正确答案是任何整数,则打印 ?.


输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 ... A_N
  • 第一行包含两个空格分隔的整数 N (1 ≦ N ≦ 10^5) 和 M (1 ≦ M ≦ 10^5).
  • 第二行包含 N 空格分隔的整数 A_1, A_2, ..., A_N. 对于每个 i (1 ≦ i ≦ N), A_i (0 ≦ A_i ≦ M) 代表的答案 i^{th} 学生。

输出

如果高桥先生假设正确答案是某个整数 X,打印值 X 在一行中。否则,打印 ?。确保在输出末尾打印换行符。

部分积分

此问题可能会获得部分分数:

  • 40 通过满足以下条件的测试集将获得积分 N ≦ 100, M ≦ 100.
  • 另一个 在没有额外限制的情况下通过测试集将获得 60 分数。

入力例1

3 2
2 1 2

出力例1

2

入力例2

4 2
2 1 2 1

出力例2

?

入力例3

10 1
0 0 0 0 0 0 1 1 1 1

出力例3

0

入力例4

10 5
0 1 2 3 4 5 5 5 5 5

出力例4

?