#include "grader.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
int cnt(int x) { return 1; }
void say_answer(int v) { cerr << "Ans is " << v << '\n'; }
int kth(int i) { return 1; }
#else
#define DE(...) 0
#define deubg(...) 0
#endif
const int MAX_N = 300010;
random_device rd;
mt19937 gen(rd());
void solve(int n)
{
uniform_int_distribution<int> dis(1, n);
const int lim = min(n, 60);
if (n <= 50) {
map<int,int> CT;
for (int i = 1;i <= n;++i)
CT[ kth(i) ]++;
for (auto [a, b] : CT)
if (b * 3 > n) {
say_answer(a);
return;
}
say_answer(-1);
return;
}
vector<int> id(n);
iota(AI(id), 1);
shuffle(AI(id), gen);
set<int> did;
int use = 0;
for (int x : id) {
if (use + 2 > lim) break;
++use;
int v = kth(x);
if (did.count(v)) continue;
did.insert(v);
if (cnt(v) * 3 > n) {
say_answer(v);
return;
}
++use;
}
say_answer(-1);
return;
}
