#include "bits/stdc++.h"
#include "grader.h"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
void solve(int n) {
vector<int> a(n + 1, -1);
if (n <= 50) {
for (int i = 1; i <= n; ++i) {
a[i] = kth(i);
}
for (int i = 1; i <= n; ++i) {
int c = 0;
for (int j = 1; j <= n; ++j) {
c += a[j] == a[i];
}
if (c > n / 3) {
say_answer(a[i]);
return;
}
}
say_answer(-1);
return;
}
for (int ite = 1; ite <= 30; ++ite) {
int x = rand(1, n);
while (a[x] != -1) {
x = rand(1, n);
}
a[x] = kth(x);
int c = cnt(a[x]);
if (c > n / 3) {
say_answer(a[x]);
return;
}
}
say_answer(-1);
}
