#include <bits/stdc++.h> #include "prize.h" using namespace std; int smax = 0; int ans = -1; int n; void getans(int l, int r, int lval, int rval) { if (ans != -1) return; if (l > r) return; int mid = (l+r)/2; vector <int> vmid = ask(mid); if (vmid[0] + vmid[1] == 0) { ans = mid; return; } if (vmid[0] + vmid[1] == smax) { if (vmid[0] > lval) getans(l,mid-1,lval,vmid[1]); if (vmid[1] > rval) getans(mid+1,r,vmid[0],rval); return; } int curr = mid+1; int curl = mid-1; vector <int> resr,resl; bool okl = false; bool okr = false; while (curr <= r) { resr = ask(curr); if (resr[0] + resr[1] == 0) { ans = curr; return; } if (resr[0] + resr[1] == smax) { okr = true; break; } curr++; } while (curl >= l) { resl = ask(curl); if (resl[0] + resl[1] == 0) { ans = curl; return; } if (resl[0] + resl[1] == smax) { okl = true; break; } curl--; } if (okr) { getans(curr, r, resr[0], rval); } if (okr) { getans(l, curl, lval, resl[1]); } } int find_best(int N) { int n = N; vector <int> res; for(int i = 0; i < min(n,500); i++) { res = ask(i); smax = max(smax,res[0] + res[1]); } getans(0,n-1,0,0); return ans; }