#include #define pr pair #define f first #define s second #define ll long long #define mp make_pair #define pii pr #define piii pr using namespace std; int rd() { char c=getchar_unlocked(); while(c<'0'||c>'9') c=getchar_unlocked(); int r=0; while(c>='0'&&c<='9') { r=r*10+(c^48); c=getchar_unlocked(); } return r; } void opp(int x) { if(x>=10) opp(x/10); putchar_unlocked('0'+x%10); } void op(int x) { opp(x); putchar_unlocked('\n'); } struct node { int l,r; int mx; } nd[1100006]; int t; void bd(int i,int l,int r) { node&x=nd[i]; x.l=l; x.r=r; x.mx=0; if(l==r-1) return; bd(i*2,l,l+r>>1); bd(i*2+1,l+r>>1,r); } void st(int i,int l,int v) { node&x=nd[i]; x.mx=max(x.mx,v); if(x.l==x.r-1) return; int m=x.l+x.r>>1; if(l=l&&x.r<=r) return x.mx; int m=x.l+x.r>>1,rt=0; if(lm) rt=max(rt,ask(i*2+1,l,r)); return rt; } vector e[500005]; int dp[500005]; int fa[19][500005]; pii gr[19][500005]; pii gl[19][500005]; int hr[19][500005]; int hl[19][500005]; int pd[1000006]; int dt[500005]; int tl[500005]; int tr[500005]; vector alv[500005]; vector arv[500005]; int ras[1000006]; vector ql[500005]; vector qr[500005]; void dfs(int x,int p=0,int d=1) { dp[x]=d; fa[0][x]=p; for(int to:e[x]) if(to!=p) dfs(to,x,d+1); } int lca(int x,int y) { if(dp[x]=0;i--) if(dp[x]-(1<=dp[y]) x=fa[i][x]; if(x==y) return x; for(int i=18;i>=0;i--) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y]; return fa[0][x]; } pii fd(int l,int r) { int h=pd[r-l]; return min(gr[h][l],gl[h][r]); } int fmx(int l,int r) { int h=pd[r-l]; return max(hr[h][l],hl[h][r]); } int main() { freopen("query.in","r",stdin); freopen("query.out","w",stdout); ios_base::sync_with_stdio(0); int n=rd(); int ux,vx; for(int i=1;i=0) gl[i][j]=min(gl[i-1][j],gl[i-1][j-(1<<(i-1))]); } } for(int i=1;i<19;i++) { for(int j=0;j<=n;j++) { if(j+(1<=0) hl[i][j]=max(hl[i-1][j],hl[i-1][j-(1<<(i-1))]); } } for(int i=0;i<19;i++) for(int j=1< v; v.push_back(0); for(int i=1;i0;i--) { while(v.back()!=n) { if(dt[v.back()]k) qr[k].push_back(mp(i*2,mp(l+k,g.s))); else ras[i*2]=g.f; if(r-g.s>=k) ql[k].push_back(mp(i*2+1,mp(g.s,r-k+1))); else ras[i*2+1]=g.f; } bd(1,0,n); for(int i=n;i>0;i--) { for(pii j:alv[i]) st(1,j.f,j.s); for(piii j:ql[i]) ras[j.f]=ask(1,j.s.f,j.s.s); } bd(1,0,n); for(int i=n;i>0;i--) { for(pii j:arv[i]) st(1,j.f,j.s); for(piii j:qr[i]) ras[j.f]=ask(1,j.s.f,j.s.s); } for(int i=0;i