include <bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

define mp make_pair

const int inf = 1e9; void build(int n,int l,int r){ if(l==r){ t[v]=a[r]; return; } push(v); int mid = (l+r)2; build(v*2,l,mid); build(v*2+1,mid+1,r); t[v]=max(t[v*2],t[v*2]+1); } void push(int v){ if(keep[v]==-1){ return; } t[v*2]=t[v*2+1]=keep[v]; keep[v*2]=keep[v*2+1]=keep[v]; keep[v]=-1; } int get(int v,int l,int r,int lx,int rx){ if(r < lx || rx < l){ return -inf; } if(lx<=l || r<=rx){ return t[v]; } push(v); int mid =(l+r)/2; int mx1 = get(v*2,l,mid,lx,rx); int mx2 = get(v*2,mid+1,r,lx,rx); return max(mx1,mx2);

} void upd(int v,int l,int r,int pos,int val){ if(l == r){ t[v]=val; return; } push(v); int mid = (l+r)/2; if(pos<=mid){ upd(v*2+1,mid+1,r,pos,val); } else upd(v*2,l,mid,pos,val); return max(t[v*2],t[v*2+1]); } void upd_seg(int v,int l,int r,int lx,int rx,int val){ if(r < lx || rx < l){ return; } if(lx<=l && r<=rx){ t[v]=val; keep[v]=val; return; } push(v); int mid = (l+r)/2; upd_seg(v*2,l,mid,lx,rx,val); upd_seg(v*2+1,mid+1,r,lx,rx,val);

t[v]=max(t[v*2],t[v*2+1]);

}

int main() {

return 0;

}