#include using namespace std; #define fi first #define se second typedef long long ll; const int N=5e5+5; int n,tot,Q,ans[N]; vectorg[N]; set>nd[N]; struct OP{int l,r,k,v;}op[N*25]; bool cmp(paira,pairb) { if(a.fi!=b.fi)return a.fib.se; } void dfs(int u,int f,int d) { vector>nw; nd[u].emplace(u,u),nw.emplace_back(u,u); for(int v:g[u])if(v!=f) { dfs(v,u,d+1); if(nd[v].size()>nd[u].size())swap(nd[u],nd[v]); for(auto i:nd[v]) { int l,r;tie(l,r)=i; int nl=l,nr=r; auto it=nd[u].lower_bound({l,r}); if(it!=nd[u].end()) { if(it->fi==r+1)nr=it->se,nd[u].erase(it); } it=nd[u].lower_bound({l,r}); if(it!=nd[u].begin()) { --it; if(it->se==l-1)nl=it->fi,nd[u].erase(it); } nd[u].emplace(nl,nr); if(nl!=l||nr!=r)nw.emplace_back(nl,nr); } } // cerr<mx) op[++tot]={nw[i].fi,nw[i].se,nw[i].se-nw[i].fi+1,d},mx=nw[i].se; } struct fwt { int t[N]; void add(int x,int y){while(x<=n)t[x]=max(t[x],y),x+=x&-x;} int ask(int x){int r=0;while(x)r=max(r,t[x]),x&=x-1;return r;} void clr(int x){while(x<=n&&t[x])t[x]=0,x+=x&-x;} }t; void solve(int l,int r) { if(l>=r)return; int cq=0; for(int i=l;i<=r;++i)if(op[i].v<0)++cq; if(!cq) { sort(op+l,op+r+1,[&](const OP&a,const OP&b) {return a.r>b.r||a.r==b.r&&a.v>b.v;}); return; } int mid=l+r>>1; solve(l,mid),solve(mid+1,r); for(int i=mid+1,j=l;i<=r;++i) { while(j<=mid&&op[j].r>=op[i].r) { if(op[j].v>0)t.add(op[j].l,op[j].v); ++j; } if(op[i].v<0)ans[-op[i].v]=max(ans[-op[i].v],t.ask(op[i].l)); } for(int j=l;j<=mid;++j)t.clr(op[j].l); inplace_merge(op+l,op+mid+1,op+r+1, [&](const OP&a,const OP&b){return a.r>b.r||a.r==b.r&&a.v>b.v;}); } int main() { freopen("query.in","r",stdin); freopen("query.out","w",stdout); scanf("%d",&n); for(int i=1,a,b;i=op[j].l&&r<=op[j].r&&k<=op[j].k) // ans=max(ans,op[j].v); // printf("%d\n",ans); } sort(op+1,op+tot+1,[&](const OP&a,const OP&b){return a.k>b.k||a.k==b.k&&a.v>b.v;}); solve(1,tot); for(int i=1;i<=Q;++i)printf("%d\n",ans[i]); }