#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
void solve(int n)
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bool> occ(n+1);
if (n <= 50){
map<int, int> mp;
REP1(i, n){
mp[kth(i)]++;
}
for (auto pp:mp){
if (pp.s > n/3){
say_answer(pp.f);
return;
}
}
say_answer(-1);
return;
}
int rem = n;
REP(i, 30){
if (rem == 0) break;
int pp = rng()%n+1;
while(occ[pp]){
pp = rng()%n+1;
}
occ[pp] = 1;
rem--;
int nipple = kth(pp);
if (cnt(nipple) > n/3) {
say_answer(nipple);
return;
}
}
say_answer(-1);
/// insert your code
/// for example
/*if(cnt(kth(1)) > n / 3) say_answer(kth(1));
else say_answer(-1);
*/
}
