#include <iostream>
#include <vector>
#include "prize.h"
using namespace std;
int tot, Ans;
vector<int> res;
void Solve(int l, int r, int k, int cnt){
vector<int> rs;
if (cnt == 0 or l == r)
return;
int mid = (l + r) / 2, m1 = mid;
rs = ask(mid);
// cout<<l<<" "<<mid<<" "<<r<<" "<<k<<" "<<cnt<<" "<<rs[0]<<" "<<rs[1]<<endl;
if (rs[0] + rs[1] != tot){
Ans += (rs[0] + rs[1] == 0) * mid;
while (m1 < r - 1){
rs = ask(++m1);
Ans += (rs[0] + rs[1] == 0) * m1;
if (rs[0] + rs[1] != tot)
break;
}
if (m1 == r - 1 and rs[0] + rs[1] != tot)
m1++;
// cout<<"here "<<m1<<" "<<rs[0]<<" "<<rs[1]<<endl;
if (m1 == r)
Solve(l, mid, k, cnt - (m1 - mid));
else
Solve(l, mid, k, k - rs[1] - (m1 - mid));
Solve(m1, r, rs[1], cnt - (k - rs[1]));
return;
}
Solve(l, mid, k, k - rs[1]);
Solve(mid, r, rs[1], cnt - (k - rs[1]));
}
int find_best(int n){
srand(time(0));
for (int i=1;i<=20;i++){
int id = rand() % n;
res = ask(id);
tot = max(tot, res[0] + res[1]);
}
Solve(0, n, tot, tot);
return Ans;
}
