#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF=1e9;
const int MX=1e5;
map<int, vi> mem;
map<int, map<int, set<int>>> bst;
int sm;
int n;
vi LB;
int SEG[MX*4], LAZY[MX*4];
void buildSeg(int p=0, int l=0, int r=n-1) {
SEG[p] = n-1;
LAZY[p] = n-1;
if(l == r) return;
int m=(l+r)/2;
buildSeg(p*2+1,l,m);
buildSeg(p*2+2,m+1,r);
}
void setSeg(int i, int j, int v, int lazy=n-1, int p=0, int l=0, int r=n-1) {
if(j > i) return;
SEG [p] = min(SEG [p], lazy);
LAZY[p] = min(LAZY[p], lazy);
if(j < l || i > r) return;
if(i <= l && j >= r) {
SEG [p] = min(SEG [p], v);
LAZY[p] = min(LAZY[p], v);
return;
}
int m = (l+r)/2;
setSeg(i,j,v,LAZY[p],p*2+1,l,m);
setSeg(i,j,v,LAZY[p],p*2+2,m+1,r);
SEG [p] = min(SEG[p*2+1], SEG[p*2+2]);
LAZY[p] = n-1;
}
int getSeg(int i, int lazy=n-1, int p=0, int l=0, int r=n-1) {
SEG [p] = min(SEG [p], lazy);
LAZY[p] = min(LAZY[p], lazy);
if(i < l || i > r) return INF;
if(l == r) return SEG[p];
int m = (l+r)/2;
int a = getSeg(i,LAZY[p],p*2+1,l,m);
int b = getSeg(i,LAZY[p],p*2+2,m+1,r);
LAZY[p] = n-1;
return min(a,b);
}
vi Ask(int i) {
if(mem.count(i)) return mem[i];
vi ret = ask(i);
if(ret[0]+ret[1] == sm) {
setSeg(0,ret[0]-1,i-1);
}
return mem[i] = ret;
}
int find_best(int N) {
n = N;
int sq = ceil(sqrt(n))+2;
int mn = min(sq*2+2, n);
sm = 0;
RE(i,mn) {
vi res = Ask(i);
sm = max(sm, res[0]+res[1]);
}
vi g; g.assign(n,-1);
vi J;
RE(i,n) J.pb(i);
buildSeg();
RE(i,sm) {
if(g[i] != -1) continue;
int lb=0, ub=getSeg(i);
if(i) lb=g[i-1]+1;
while(lb != ub) {
int mid=(lb+ub+1)/2;
vi res = Ask(mid);
if(res[0] + res[1] == sm) {
if(res[0] > i) ub=mid-1;
else lb=mid+1;
if(lb == ub) g[i] = lb;
} else {
int j = J[mid];
vi update;
while(1) {
res = Ask(j);
if(res[0] + res[1] == sm) {
if(res[0] == i) {
lb = ub = j+1;
}
break;
}
update.pb(j);
if(j == 0) {
lb = ub = 0;
break;
}
j = J[j-1];
}
FOR(k,update) J[k] = j;
if(lb == ub) {
REP(k,lb,mid+1) {
g[i+k-lb] = k;
}
if(mid == n-1) break;
res = Ask(++mid);
while(res[0]+res[1] != sm) {
g[i+mid-lb] = mid;
if(mid == n-1) break;
res = Ask(++mid);
}
} else {
res = Ask(j);
if(res[0] > i) ub=j-1;
else lb=mid+1;
if(lb == ub) g[i] = lb;
}
}
}
vi res = Ask(g[i]);
if(res[0]+res[1] == 0) return g[i];
}
return 0;
}
