#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;
ll n, m, k = 0;
// Q <= 60 randomizationdan basqa aglima hecne gelmir
mt19937 rng(time(0));
#include "grader.h"
void solve(int _n){
n = _n;
set<ll>s;
ll tt = 30;
while(tt --){
ll x = rng() % n + 1;
if(s.count(x)) continue;
s.insert(x);
ll el = kth(x);
ll ct = cnt(el);
if(ct > n / 3) return say_answer(el), void();
}
say_answer(-1);
}
// void _() {
// }
// signed main() {
// cin.tie(0)->sync_with_stdio(0);
// ll t = 1;
// cin >> t;
// while(t --) _();
// }
