#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int a, int b){
return a+rng()%(b-a+1);
}
void solve(int n) {
pair<int, int> x={0, -1};
vector<int> v;
for (int i=1; i<=n; ++i) v.push_back(i);
shuffle(v.begin(), v.end(), rng);
if (n <= 50) {
map<int, int> cnt;
for (int i=1; i<=n; ++i) {
int val=kth(i);
++cnt[val];
if (cnt[val] > n/3) {
say_answer(val);
return;
}
}
say_answer(-1);
return;
}
for (int i=0; i<min(n, 30); ++i) {
int r=v[i], val=kth(r);
x=max(x, {cnt(val), val});
}
if (x.first > n/3) say_answer(x.second);
else say_answer(-1);
}
