#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
void solve(int n)
{
/// insert your code
/// for example
int a[n+2]={0};
if(n<=50)
{
map<int,int> cnt;
for(int i=1;i<=n;i++)cnt[kth(i)]++;
for(auto it:cnt)
{
if(it.second>(n/3))
{
say_answer(it.first);
return;
}
}
say_answer(-1);
return;
}
for(int i=1;i<=n;i++)a[i]=-1;
int lm=n/3;
srand(time(0));
for(int ip=0;ip<30;ip++)
{
int j=rand()%n + 1;
while(a[j]!=-1)
{
j=rand()%n+1;
}
a[j]=kth(j);
if(cnt(a[j])>lm)
{
say_answer(a[j]);
return;
}
}
say_answer(-1);
}
