#include <vector>
#include <algorithm>
#include <map>
#include <random>
#include <chrono>
#include "grader.h"
using namespace std;
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
using pii = pair<int, int>;
void solve(int n) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
map<int, bool> vis;
map<int, int> mp;
for (int i = 1; i <= 55 && i <= n; i++) {
int pos = abs(int(rng())) % n + 1;
if (!vis[pos]) {
vis[pos] = true;
mp[kth(pos)]++;
}
}
vector<pii> v;
for (auto [ val, fr ] : mp)
v.push_back({ -fr, val });
sort(all(v));
for (int i = 0; i < 5 && i < int(v.size()); i++) {
if (cnt(v[i].se) > n / 3) {
say_answer(v[i].se);
return;
}
}
say_answer(-1);
}
