#include #include #include #define N 110000 #define pr pair #define lson l,mid,no<<1 #define rson mid+1,r,no<<1|1 #define mod 1000000007ll using namespace std; typedef long long ll; int dis[N<<1],len; pr L[N]; ll sum[N<<3],cov[N<<3]; ll P[N],S[N]; void Pushdown(int no,int len) { if(cov[no]) { cov[no<<1]+=cov[no]; cov[no<<1|1]+=cov[no]; sum[no<<1]+=cov[no]*(len-(len>>1)); sum[no<<1|1]+=cov[no]*(len>>1); cov[no]=0; } } void Pushup(int no) { sum[no]=sum[no<<1]+sum[no<<1|1]; } void update(int l,int r,int no,int st,int en) { if(st<=l&&r<=en) { cov[no]++; sum[no]+=r-l+1; } else { int mid=l+r>>1; Pushdown(no,r-l+1); if(en<=mid) update(lson,st,en); else if(st>mid) update(rson,st,en); else update(lson,st,en),update(rson,st,en); Pushup(no); } } int query(int l,int r,int no,int k) { if(l==r) return sum[no]; else { int mid=l+r>>1; Pushdown(no,r-l+1); if(k<=mid) return query(lson,k); else return query(rson,k); } } int main() { int c,T; int n,i,l,r; scanf("%d",&T); P[1]=1; for(i=2;i