#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> possible;
int mx;
vi done[200005];
vi asky(int ind){
// cout << ind << endl;
if(done[ind].size()) return done[ind];
return done[ind] = ask(ind);
}
void solve(int l,int r,int lcnt,int rcnt){
// cout << l << " " << r << " " << lcnt << " " << rcnt << endl;
if(l > r) return;
if(lcnt+rcnt == mx) return;
int mid = (l+r)/2;
int m = mid;
int bizz = 0;
while(mid >= l){
vi gg = asky(mid);
if(gg[0]+gg[1] == mx){
solve(l,mid-1,lcnt,gg[1]);
solve(m+1,r,gg[0]+bizz,rcnt);
return;
}
possible.pb({gg[0]+gg[1],mid});
bizz++;
mid--;
}
solve(m+1,r,lcnt+bizz,rcnt);
}
int find_best(int n) {
vi bruh = {175038, 164912, 48447, 56204, 130467, 61981, 156795, 71155, 165755, 46492, 14913, 121820, 48037, 14809, 18188, 47090, 44335, 70042, 63699, 112155, 92988, 195226, 83797, 177680, 156562, 91803, 74301, 131570, 93639, 30707, 117677, 164693, 60304, 82393, 50874, 42681, 196535, 114714, 130612, 8175, 1961, 167732, 25952, 126880, 35181, 4129, 195226, 65614, 93274, 93049, 106533, 150951, 10812, 158910, 141820, 34594, 129541, 149736, 13599, 191657, 182831, 191057, 96180, 125258, 19449, 71635, 153028, 182528, 111578, 4250, 165230, 3356, 39309, 332, 175116, 196923, 95308, 104449, 92485, 196292, 161180, 194584, 87349, 91014, 102108, 138598, 183452, 120325, 103919, 145804, 149462, 181941, 13311, 151831, 40995, 24088, 1702, 78417, 20497, 137355, 147324, 70197, 29274, 107710, 56993, 27165, 79201, 48319, 67302, 81015, 61015, 140652, 6451, 144012, 66265, 196066, 44906, 98585, 80597, 194841, 78730, 198086, 160990, 26219, 21458, 31211, 4117, 139031, 93154, 168228, 29535, 153990, 192236, 189054, 132102, 93027, 62180, 150788, 140895, 31431, 26133, 180233, 55568, 121279, 150362, 78361, 171501, 81164, 181689, 143013, 93429, 89467, 182020, 92448, 182745, 115189, 83809, 544, 8572, 175359, 136681, 62664, 48643, 163232, 1486, 90043, 76547, 34492, 121612, 108895, 52498, 159681, 44550, 55494, 174209, 111888, 14058, 151376, 127349, 111296, 71294, 80716, 100, 16638, 159372, 76664, 33592, 35855, 94299, 66743, 38793, 62754, 74804, 28105, 110297, 31273, 65903, 114041, 24099, 142849};
for(int i = 0; i < 300; i++){
int ind = bruh[i]%n;
vi gg = asky(ind);
mx = max(mx,gg[0]+gg[1]);
}
solve(0,n-1,0,0);
sort(all(possible));
return possible[0].S;
}
