#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)s.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
int a[10000];
map<int,int> M;
int q;
int getEle(int i){
if(!q) return 0;
if(a[i]!=-1) return a[i];
q--; return a[i]=kth(i);
}
int getCnt(int a){
if(!q) return 0;
if(M.find(a)!=end(M)) return M[a];
q--; return M[a]=cnt(a);
}
void solve(int n){
srand(time(0));
M.clear(); q = 60;
for(int i = 1; i <= n; i++) a[i]=-1;
if(n<=50){
if(n==1){
say_answer(kth(1));
return;
}
for(int i = 1; i <= n/2; i++){
int x = kth(i);
if(cnt(x) > n / 3){
say_answer(x); return;
}
}
say_answer(-1);
return;
}
vi v(n,0); iota(all(v),1);
random_shuffle(all(v));
for(auto i : v){
if(!q) break;
int x = getEle(i);
if(getCnt(x) > n/3){
say_answer(kth(1));
return;
}
}
say_answer(-1);
}
