집정관

레메에서 집정관 선거가 열린다. 이 선거에는 $N$명의 선거인이 있고, 각 선거인은 서로 다른 $1\,000\,000\,000$명의 후보 중 하나에게 투표할 수 있다. 후보가 당선되려면 투표의 $1/3$을 초과하는 표를 받아야 한다(레메는 매년 집정관 두 명을 선출하기 때문에 이렇게 된다). 당신은 투표 조작을 꿈꾸는 사람이다. 조작을 더 효과적으로 하려면 당선 가능성이 있는 후보를 최소 한 명 알아야 한다. 안타깝게도 각 선거인이 누구에게 투표했는지는 공개되지 않는다. 대가를 치르지 않고서는 알 수 없다. 게다가 이미 개표를 마친 전임 집정관들은 특정 후보가 받은 표의 수를 알려줄 수 있다. 물론 이것도 대가를 치러야 한다.

더 형식적으로, 값이 $0$ 이상 $1\,000\,000\,000$ 미만인 $N$개의 정수 $v[1] \dots v[N]$로 이루어진 숨겨진 수열 $v$를 생각하자. 이 수열에 대해 두 종류의 질의를 할 수 있다.

• 수열에서 특정 원소 $v[i]$의 값을 알아낼 수 있다.
• 특정 값 $x$가 수열에 몇 번 나타나는지 알 수 있다.

수열에서 $N/3$번을 초과해 나타나는 값 $x$를 찾아야 하며, 수행하는 질의의 수는 충분히 적어야 한다.

$N$이 주어졌을 때, 주어진 질의를 사용해 선거의 당선자를 하나 찾거나, 당선자가 존재하지 않는다고 알려라.