#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "prize.h"
#endif
using namespace std;
// NB: ask(i) returns a two-elem vector<int>
const int MAXN=200000;
bool asked[MAXN];
pair<int,int> answers[MAXN];
#ifdef ARTHUR_LOCAL
vector<int> real_deal;
vector<int> ask(int n)
{
int ans1=0;
int ans2=0;
for(int i=0; i<n; i++)
{
if(real_deal[i]<real_deal[n]) ans1++;
}
for(int i=n; i<8; i++)
{
if(real_deal[i]<real_deal[n]) ans2++;
}
return {ans1,ans2};
}
#endif
pair<int,int> get_ans(int n)
{
//cout << n << endl;
if(asked[n]) return answers[n];
cout << "Q!" << endl;
asked[n]=1;
vector<int> cur = ask(n);
answers[n] = {cur[0],cur[1]};
return answers[n];
}
int find_best(int n)
{
// query 30 random places in order to determine the minimum thing
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1,1000000000);
int max_side=0;
for(int i=0; i<100; i++) // should be less than 2**(-30) of failure to find the right value
{
pair<int,int> cur = get_ans(dis(gen)%n);
max_side = max(max_side,cur.first+cur.second);
}
int left = 0;
int right = n-1;
while(true)
{
pair<int,int> cur = get_ans(left);
if(cur.first + cur.second == 0) return left;
if(cur.first + cur.second == max_side) break;
left++;
}
while(true)
{
pair<int,int> cur = get_ans(right);
if(cur.first + cur.second == 0) return right;
if(cur.first + cur.second == max_side) break;
right--;
}
//cout << left << " " << right << endl;
vector<pair<int,int>> I = {make_pair(left,right)};
while(true)
{
vector<pair<int,int>> new_I;
for(auto i:I)
{
int left = i.first;
int right = i.second;
// cout << left << " " << right << endl;
int lmid = int((left+right)/2);
int rmid = lmid + 1;
bool do_left=1;
bool do_right=1;
while(true)
{
pair<int,int> cur = get_ans(lmid);
if(cur.first + cur.second == 0) return lmid;
if(cur.first + cur.second == max_side) break;
if(cur.first == 0) do_left=0;
if(cur.second == 0) do_right=0;
// if(get_ans(lmid).first == get_ans(left).first) break;
lmid--;
}
while(true)
{
pair<int,int> cur = get_ans(rmid);
if(cur.first + cur.second == 0) return rmid;
if(cur.first + cur.second == max_side) break;
if(cur.first == 0) do_left=0;
if(cur.second == 0) do_right=0;
// if(get_ans(right).first == get_ans(rmid).first) break;
rmid++;
}
//cout << "LR: " << lmid << " " << rmid << endl;
if(do_left && get_ans(lmid).first > get_ans(left).first) new_I.push_back({left,lmid});
if(do_right && get_ans(right).first > get_ans(rmid).first) new_I.push_back({rmid,right});
}
I = new_I;
}
}
#ifdef ARTHUR_LOCAL
int main()
{
cout << sqrt(200000) << endl;
real_deal = {1,2,2,3,3,3,3,3};
do
{
for(int i=0; i<8; i++)
{
asked[i]=0;
}
for(auto i:real_deal) cout << i << " ";
cout << endl << find_best(8) << endl;
} while(next_permutation(real_deal.begin(),real_deal.end()));
}
#endif
