#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair < int, int > PII;
int N;
int Candy_Sum = 0;
unordered_map < int, bool > Sel;
unordered_map < int, pair < int, int > > mp;
///
inline PII Get_Ans (int pos)
{
if(Sel[pos])
return mp[pos];
vector < int > res = ask(pos);
Sel[pos] = 1, mp[pos] = {res[0], res[1]};
return {res[0], res[1]};
}
inline bool IsDiamond (PII X)
{
return ((X.first + X.second) == 0);
}
inline bool IsCandy (PII X)
{
return ((X.first + X.second) == Candy_Sum);
}
///
inline int Go (int Left, int Right)
{
if(Left > Right)
return 0;
if(Left == Right)
return Left;
int Mid = ((Left + Right) >> 1);
PII Now = Get_Ans(Mid);
if(IsDiamond(Now))
return Mid;
if(Now.first)
return Go(Left, Mid - 1);
return Go(Mid + 1, Right);
}
inline int F (int Left, int Right, int less_to_left, int less_to_right)
{
if(Left > Right)
return 0;
if(Left == Right)
{
if(IsDiamond(Get_Ans(Left)))
return Left;
return 0;
}
int Mid = ((Left + Right) >> 1);
PII Now = Get_Ans(Mid);
if(IsDiamond(Now))
return Mid;
int i = Mid - 1, j = Mid + 1, pos = 0;
bool found = 0;
if(IsCandy(Now))
found = 1, pos = Mid;
///
while(!found && (i >= Left || j <= Right))
{
if(i >= Left)
{
PII curr = Get_Ans(i);
if(IsDiamond(curr))
return i;
if(!IsCandy(curr))
--i;
else
{
found = 1, pos = i, Now = curr;
break;
}
}
if(j <= Right)
{
PII curr = Get_Ans(j);
if(IsDiamond(curr))
return j;
if(!IsCandy(curr))
++j;
else
{
found = 1, pos = j, Now = curr;
break;
}
}
}
///
if(!found)
return 0;
Mid = pos;
int ans = 0;
int ext_left = Now.first - less_to_left;
int ext_right = Now.second - less_to_right;
if(!ext_left && !ext_right)
return 0;
if(ext_left && ext_right)
{
if(ext_left > ext_right)
{
ans = F(Left, Mid - 1, less_to_left, Now.second);
if(!ans)
ans = F(Mid + 1, Right, Now.first, less_to_right);
}
else
{
ans = F(Mid + 1, Right, Now.first, less_to_right);
if(!ans)
ans = F(Left, Mid - 1, less_to_left, Now.second);
}
}
else
{
if(ext_left)
ans = F(Left, Mid - 1, less_to_left, Now.second);
else
ans = F(Mid + 1, Right, Now.first, less_to_right);
}
return ans;
}
int find_best(int n)
{
N = n;
for(int i = 0; i < min(N, 476); ++i)
{
PII Now = Get_Ans(i);
if(IsDiamond(Now))
return i;
Candy_Sum = max(Candy_Sum, Now.first + Now.second);
}
if(Candy_Sum == 1)
return Go(0, N - 1);
return F(0, N - 1, 0, 0);
}
