#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
unordered_map<int,int> fr1;
unordered_map<int,bool> bl1;
unordered_map<int,int> fr2;
unordered_map<int,bool> bl2;
int maxq;
int cntq;
int actual_kth(int k)
{
if(bl1[k]==0)
{
fr1[k]=kth(k);
bl1[k]=1;
cntq++;
}
return fr1[k];
}
int actual_cnt(int x)
{
if(bl2[x]==0)
{
fr2[x]=cnt(x);
bl2[x]=1;
cntq++;
}
return fr2[x];
}
void solve(int n)
{
cntq=0;
fr1.clear();
bl1.clear();
fr2.clear();
bl2.clear();
maxq=min(60,n);
mt19937 rnd(82396293);
while(cntq+2<=maxq)
{
int x = 1 + (rnd())%n;
if(bl1[x]==0)
{
int care = actual_kth(x);
if(actual_cnt(care) > n/3)
{
say_answer(care);
return;
}
}
}
say_answer(-1);
return;
}
