#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair < int, int > PII;
int N, V = 0;
int Candy_Sum = 0;
inline PII Get_Ans (int pos)
{
vector < int > res = ask(pos);
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;
}
if(Left == Right - 1)
{
for(int i = Left; i <= Right; ++i)
if(IsDiamond(Get_Ans(i)))
return i;
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 && !IsCandy(Get_Ans(i)))
--i;
if(!found && i >= Left)
found = 1, pos = i;
while(!found && j <= Right && !IsCandy(Get_Ans(j)))
++j;
if(!found && j <= Right)
found = 1, pos = j;
if(!found)
return 0;
Mid = pos;
Now = Get_Ans(Mid);
int ans = 0;
if(Now.first != less_to_left)
ans = F(Left, Mid - 1, less_to_left, Now.second);
if(!ans && Now.second != less_to_right)
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, 501); ++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);
}
