/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はテストの結果を採点しています。ところが、高橋君はある問題の正解を忘れてしまいました。この問題は、N 人が解答していて、それぞれの人の答えは 0 以上 M 以下の整数でした。高橋君は、半分を超える人が同じ答えだった場合、それを正解とすることにしました。
N 人のこの問題に対する解答が与えられるので、高橋君は何を正解とするか出力してください。ただし、高橋君が正解を決められない場合、? を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), M (1 ≦ M ≦ 10^5) が空白区切りで与えられる。
- 2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には、i 番目の人の解答を表す整数 A_i (0 ≦ A_i ≦ M) が与えられる。
出力
高橋君が正解とする整数を 1 行に出力せよ。ただし、高橋君が正解を決められない場合、1 行に ? を出力せよ。出力の末尾に改行を入れること。
部分点
この問題には部分点が設定されている。
- N ≦ 100, M ≦ 100 を満たすデータセットに正解した場合は、40 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 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
?
Problem Statement
Mr. Takahashi is marking examination papers of his students. Unfortunately, he has forgotten the correct answer to a certain question.
N students answered this question by an integer between 0 and M, inclusive. He has decided to assume the correct answer to be the integer X if more than half of the students answered X.
You are given the answers of the N students to this question. If he is going to assume the correct answer to be some integer X, print the value of X. If he is unable to assume the correct answer to be any integer, print ?.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
- The first line contains two space-separated integers N (1 ≦ N ≦ 10^5) and M (1 ≦ M ≦ 10^5).
- The second line contains N space-separated integers A_1, A_2, ..., A_N. For each i (1 ≦ i ≦ N), A_i (0 ≦ A_i ≦ M) represents the answer of the i^{th} student.
Output
If Mr. Takahashi is going to assume the correct answer to be some integer X, print the value of X in a single line. Otherwise, print ?. Be sure to print a newline at the end of output.
Partial Points
Partial points may be awarded in this problem:
- 40 points will be awarded for passing the test set satisfying N ≦ 100, M ≦ 100.
- Another 60 points will be awarded for passing the test set without additional constraints.
入力例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
?