#include #define N 500011 using namespace std; vector G[N];int n,q,a[N]; namespace IO { char Is[(1<<21)+10],Os[(1<<21)+10];int Ipt=1<<21,Opt; char gc() { if(Ipt==(1<<21))Is[fread(Is,1,1<<21,stdin)]=0,Ipt=0; // putchar(Is[Ipt]); return Is[Ipt++]; } void flush(){fwrite(Os,1,Opt,stdout);Opt=0;} void pc(char x) { Os[Opt++]=x; if(Opt==(1<<21))flush(); } // #define gc getchar // #define pc putchar int read() { int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c<='9'&&c>='0')x=x*10+c-'0',c=gc(); return x; } void write(int x){if(x<10)pc(x+'0');else write(x/10),pc(x%10+'0');} } using namespace IO; namespace lca { int dep[N],st[21][N],h[N],dfn[N],clk; void dfs(int u,int F) {//printf("dfs(%d,%d)\n",u,F); dep[u]=dep[F]+1;dfn[u]=++clk; for(int v:G[u])if(v^F) { h[clk]=u; dfs(v,u); } } void proc() { dfs(1,0); for(int i=1;idfn[v])swap(u,v); int logl=__lg(dfn[v]-dfn[u]); int u1=st[logl][dfn[u]],u2=st[logl][dfn[v]-(1< vu[N]; int ans[N]; struct kueri{int l,r,k,id;}; vector vk[N]; namespace sgt { int mx[N*4],D; void modi(int k,int p) {//printf("modi(%d,%d)\n",k,p); k+=D; mx[k]=p;while(k>>=1)mx[k]=max(mx[k<<1],mx[k<<1|1]); } int query(int l,int r) {//printf("query([%d,%d])\n",l,r); l+=D-1;r+=D+1;int ans=0; while(l^r^1) { if(!(l&1))ans=max(ans,mx[l^1]); if(r&1)ans=max(ans,mx[r^1]); l>>=1;r>>=1; } // printf("ans:%d\n",ans); return ans; } } int main() { freopen("query.in","r",stdin);freopen("query.out","w",stdout);//setvbuf(stdout,0,_IONBF,0); n=read(); for(int i=1;i1) { vk[k-1].push_back({l,r-1,k-1,i}); ans[i]=max(query(l,l+k-2),query(r-k+1,r-1)); } else { ans[i]=qd(l,r); } } for(int i=1;i=a[i])L[i]=L[L[i]]; for(int i=n-1;i;--i)while(R[i]a[i])R[i]=R[R[i]]; // for(int i=1;i>>>>>>>>>>>i:%d\n",i); for(node u:vu[i]) { // printf("u:{[%d,%d] v:%d}\n",u.l,u.r,u.v); Tr.add(u.r,u.r); Tl.add(n-u.l,n-u.l); sgt::modi(u.r,u.v); } for(kueri k:vk[i]) { // printf("kueri{[%d,%d],k:%d,id:%d}(%d)\n",k.l,k.r,k.k,k.id,ans[k.id]); k.l=n-Tl.query(n-k.l); k.r=Tr.query(k.r); // printf("new [%d,%d]\n",k.l,k.r); if(k.l<=k.r)ans[k.id]=max(ans[k.id],sgt::query(k.l,k.r)); // printf("ans:%d\n",ans[k.id]); } } for(int i=1;i<=q;++i)write(ans[i]),pc(10);flush(); fclose(stdin);fclose(stdout);return 0; }