#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int kth(int i);
int cnt(int x);
void say_answer(int a);
int v[1001];
void solve(int N){
if(N <= 50){
for(int i = 1; i <= N; i++){
v[i] = kth(i);
}
map<int, int> M;
for(int i = 1; i <= N; i++){
M[v[i]]++;
}
for(auto i : M){
if(i.second * 3 > N){
say_answer(i.first);
return;
}
}
say_answer(-1);
}else{
for(int j = 0; j < 30; j++){
int val = kth(rng() % N + 1);
if(cnt(val) * 3 > N){
say_answer(val);
return;
}
}
say_answer(-1);
}
}
