#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
/*static const int MIN_VALUE = 0, MAX_VALUE = (1e9) - 1;
static map<int,int> mp;
static int Q, N, a[5005];
static bool issol, answer;
void say_answer(int k)
{
cout<<k<<'\n';
}
int cnt(int k)
{
++Q;
if(!(k>=MIN_VALUE && k<=MAX_VALUE))
{
cout << "Wrong query format\n";
exit(0);
}
return mp[k];
}
int kth(int k)
{
++Q;
if(!(k>=1 && k<=N))
{
cout << "Wrong query format\n";
exit(0);
}
return a[k];
}
*/
void solve(int n)
{
map<int,bool> sel;
for(int i=1; i<=50 && i<=n; i++)
{
int x = rand();
x = x%(n-i+1) + 1;
int nrr = 0;
for(int j=1;j<=n;j++)
{
if(!sel[j])
{
++nrr;
}
if(nrr==x)
{
x=j;
break;
}
}
int val = kth(x);
int nr = cnt(val);
sel[x]=true;
if(nr>n/3)
{
say_answer(val);
return;
}
}
say_answer(-1);
}
/*int main()
{
int tests, i;
cin >> tests;
while(tests--)
{
cin >> N; mp.clear();
Q = 0; issol = 0; answer = 0;
for(i=1; i<=N; ++i) cin >> a[i], ++mp[a[i]];
for(i=1; i<=N; ++i) issol |= (mp[a[i]] > N/3);
solve(N);
}
return 0;
}
*/
