#include "grader.h"
#include <bits/stdc++.h>
// author : aykhn
using namespace std;
typedef long long ll;
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
int n;
vector<int> v;
int l;
int c = 0;
void solve(int N)
{
srand(time(0));
n = N;
v.assign(n + 1, 0);
l = 60;
c = 0;
int ans = -1;
while (l && c * 2 <= n)
{
l--;
if (!l) return;
int x = rand() % n + 1;
while (v[x]) x = rand() % n + 1;
v[x] = 1;
int y = kth(x);
int cc = cnt(y);
if (cc*3 > n)
{
ans = y;
break;
}
c++;
l--;
}
say_answer(ans);
}
