/*
___ ___ ___ ___ ___ ___ ___ _____ ___ ___ ___
/ /\ /__/\ / /\ /__/\ / /\ /__/\ / /\ / /::\ / /\ / /\ / /\
/ /::\ | |::\ / /::\ \ \:\ / /::\ | |::\ / /::\ / /:/\:\ / /::\ / /::\ / /::\
/ /:/\:\ | |:|:\ / /:/\:\ \__\:\ / /:/\:\ | |:|:\ / /:/\:\ / /:/ \:\ / /:/\:\ / /:/\:\ / /:/\:\
/ /:/ \:\ __|__|:|\:\ / /:/ \:\ ___ / /::\ / /:/~/::\ __|__|:|\:\ / /:/~/::\ /__/:/ \__\:| / /:/ \:\ / /:/ \:\ / /:/ \:\
/__/:/ \__\:\ /__/::::| \:\ /__/:/ \__\:\ /__/\ /:/\:\ /__/:/ /:/\:\ /__/::::| \:\ /__/:/ /:/\:\ \ \:\ / /:/ /__/:/ \__\:\ /__/:/ \__\:\ /__/:/ \__\:\
\ \:\ / /:/ \ \:\~~\__\/ \ \:\ / /:/ \ \:\/:/__\/ \ \:\/:/__\/ \ \:\~~\__\/ \ \:\/:/__\/ \ \:\ /:/ \ \:\ / /:/ \ \:\ / /:/ \ \:\ / /:/
\ \:\ /:/ \ \:\ \ \:\ /:/ \ \::/ \ \::/ \ \:\ \ \::/ \ \:\/:/ \ \:\ /:/ \ \:\ /:/ \ \:\ /:/
\ \:\/:/ \ \:\ \ \:\/:/ \ \:\ \ \:\ \ \:\ \ \:\ \ \::/ \ \:\/:/ \ \:\/:/ \ \:\/:/
\ \::/ \ \:\ \ \::/ \ \:\ \ \:\ \ \:\ \ \:\ \__\/ \ \::/ \ \::/ \ \::/
\__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/ \__\/
*/
#include <bits/stdc++.h>
#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll >
#define F first
#define S second
#define ld long double
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll , null_type , less<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;
const int MOD=998244353;
const int N=8e5+7;
const ll INF= 1e18+10;
long long po(ll x,ll y)
{
ll ans=1;
while(y){
if(y & 1) ans=(ans*x)%MOD;
y/=2;
x=(x*x)%MOD;
}
return ans;
}
map<ll,bool >pos;
map<ll,bool >num;
void solve(int n)
{
ll q=0;
while(q<50){
int i=(rand()%n)+1;
while(pos[i]) i=(rand()%n)+1;
ll val=kth(i);
q++;
if(q<50){
q++;
if(cnt(val)>n/3){
say_answer(val);
return;
}
}
}
say_answer(-1);
}
