//树状数组 ：利用二进制性质，可在O(logn)对区间前缀进行查询和修改操作const int N=100050;
int c[N],ans[N]; //c[n]表示a[1~n]的和，a数组省略
int lowbit(int x) //求2^k
{ return x & -x;
}
int getsum(int n) //区间查询，求a[1~n]的和
{int res = 0;while(n>0){res+=c[n];n=n-lowbit(n);}return res;
}
int change(int x) //单点更新，将a[x]的值加1
{while(x<=N){c[x]++;x+=lowbit(x);}
}
int main()
{int n;cin>>n;memset(c,0,sizeof(c));memset(ans,0,sizeof(ans));for(int i=0;i<n;i++){int x,y;cin>>x>>y;x++;ans[getsum(x)]++;change(x);}for(int i=0;i<n;i++)cout<<ans[i]<<endl;return 0;
}
//单点操作，区间更新using namespace std;
#define INF 10000000
#define lson l,mid,rt<<1 //左儿子
#define rson mid+1,r,rt<<1|1 //右儿子
const int maxn = 222222;
struct Node{ int Max,Min; //区间的最大值和最小值 int sum; //区间的和
}stree[maxn<<2];
void up(int rt){ //更新该区间的最值与和 stree[rt].Max=max(stree[rt<<1].Max,stree[rt<<1|1].Max); stree[rt].Min=min(stree[rt<<1].Min,stree[rt<<1|1].Min); stree[rt].sum=stree[rt<<1].sum+stree[rt<<1|1].sum;
}
void build(int l,int r,int rt){ //在结点i上建立区间为[l,r] if(l==r){ //叶子结点 int num; scanf("%d",&num); stree[rt].Max=stree[rt].Min=stree[rt].sum=num; return ; } int mid=(l+r)>>1; build(lson); //建立左儿子 build(rson); //建立右儿子 up(rt); //更新
}
int querymax(int a,int b,int l,int r,int rt){ //求区间[a,b]的最大值 if(a<=l&&r<=b){ //如果全包含，直接取区间最大值 return stree[rt].Max; } int mid = (r+l)>>1; int ret = -INF; if(a<=mid) ret=max(ret,querymax(a,b,lson));//如果左端点在中点的左边，找出左区间的最大值 if(mid<b) ret=max(ret,querymax(a,b,rson));//如果右端点在中点的右边，找出右区间(以及左区间)的最大值 return ret;
}
int querymin(int a,int b,int l,int r,int rt){ //求区间[a,b]的最小值 if(a<=l&&r<=b){ //如果全包含，直接取区间最小值 return stree[rt].Min; } int mid = (r+l)>>1; int ret = INF; if(a<=mid) ret=min(ret,querymin(a,b,lson));//如果左端点在中点的左边，找出左区间的最小值 if(mid<b) ret=min(ret,querymin(a,b,rson)); //如果右端点在中点的右边，找出右区间(以及左区间)的最小值 return ret;
}
int querysum(int a,int b,int l,int r,int rt){ //求区间[a,b]的和(a,b的值相同时为求单点的值) if(a<=l&&r<=b){ //如果全包含，直接取区间的和 return stree[rt].sum; } int mid = (r+l)>>1; int ret=0; if(a<=mid) ret+=querysum(a,b,lson); if(mid<b) ret+=querysum(a,b,rson); return ret;
}
void uppoint(int a,int b,int l,int r,int rt){ //单点替换,把第a个数换成b if(l==r){ stree[rt].Max=stree[rt].Min=stree[rt].sum=b; return ; } int mid =(r+l)>>1; if(a<=mid)uppoint(a,b,lson); else uppoint(a,b,rson); up(rt);
}
void upadd(int a,int b,int l,int r,int rt){ //单点增减,把第a个数增减b if(l==r){ stree[rt].sum=stree[rt].sum+b; stree[rt].Max=stree[rt].Max+b; stree[rt].Min=stree[rt].Min+b; return ; } int mid=(l+r)>>1; if(a<=mid) upadd(a,b,lson); else upadd(a,b,rson); up(rt);
}
int main()
{ //freopen("F:\\11.txt","r",stdin); int n,q; while(~scanf("%d%d",&n,&q)){ build(1,n,1);//build(l,r,rt); while(q--){ char op[10]; int a,b; scanf("%s%d%d",op,&a,&b); if(op[0]=='X'){//求区间[a,b]的最大值 printf("%d\n",querymax(a,b,1,n,1));//querymax(int a,int b,int l,int r,int rt); } else if(op[0]=='N'){//求区间[a,b]的最小值 printf("%d\n",querymin(a,b,1,n,1));//querymin(int a,int b,int l,int r,int rt); } else if(op[0]=='U'){//单点替换,把第a个数换成b uppoint(a,b,1,n,1);//uppoint(int a,int b,int l,int r,int rt); } else if(op[0]=='S'){//求区间[a,b]的和(a,b的值相同时为求单点的值) printf("%d\n",querysum(a,b,1,n,1));//querysum(int a,int b,int l,int r,int rt); } else if(op[0]=='A'){//单点增加,把第a个数增加b upadd(a,b,1,n,1); } else if(op[0]=='E'){//单点减少,把第a个数减少b upadd(a,-b,1,n,1); } } } return 0;
}
//区间更换，区间查询#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 100100;
const int INF=0x7fffffff;
using namespace std;
int lazy[maxn<<2];
int MAX[maxn<<2];
int MIN[maxn<<2];
int SUM[maxn<<2];
void PushUp(int rt) { //由左孩子、右孩子向上更新父节点SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];MAX[rt] = max(MAX[rt<<1],MAX[rt<<1|1]);MIN[rt] = min(MIN[rt<<1],MIN[rt<<1|1]);
}
void PushDown(int rt,int m) { //向下更新if (lazy[rt]) { //懒惰标记lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];SUM[rt<<1] = (m - (m >> 1)) * lazy[rt];SUM[rt<<1|1] = ((m >> 1)) * lazy[rt];MAX[rt<<1]=MAX[rt<<1|1]=lazy[rt];MIN[rt<<1]=MIN[rt<<1|1]=lazy[rt];lazy[rt] = 0;}
}
//所有的l，r，rt 带入1，n，1
void build(int l,int r,int rt) { //初始化建树lazy[rt] = 0;if (l== r) {SUM[rt]=MAX[rt]=MIN[rt]=0; //初始化为0的建树/*scanf("%d",&SUM[rt]); //边读入边建树的方法MAX[rt]=MIN[rt]=SUM[rt];*/return ;}int m = (l + r) >> 1;build(lson);build(rson);PushUp(rt);
}
void update(int L,int R,int v,int l,int r,int rt) { //将L~R区间的值置为v//if(L>l||R>r) return;if (L <= l && r <= R) {lazy[rt] = v;SUM[rt] = v * (r - l + 1);MIN[rt] = v;MAX[rt] = v;//printf("%d %d %d %d %d\n", rt, sum[rt], c, l, r);return ;}PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (L <= m) update(L , R , v , lson);if (R > m) update(L , R , v , rson);PushUp(rt);
}
int querySUM(int L,int R,int l,int r,int rt) { //求区间L~R的和if (L <= l && r <= R) {//printf("%d\n", sum[rt]);return SUM[rt];}PushDown(rt , r - l + 1);int m = (l + r) >> 1;int ret = 0;if (L <= m) ret += querySUM(L , R , lson);if (m < R) ret += querySUM(L , R , rson);return ret;
}
int queryMIN(int L,int R,int l,int r,int rt) { //求区间L~R的最小值if (L <= l && r <= R) {//printf("%d\n", sum[rt]);return MIN[rt];}PushDown(rt , r - l + 1);int m = (l + r) >> 1;int ret = INF;if (L <= m) ret = min(ret, queryMIN(L , R , lson));if (m < R) ret = min(ret,queryMIN(L , R , rson));return ret;
}
int queryMAX(int L,int R,int l,int r,int rt) { //求区间L~R的最大值if (L <= l && r <= R) {//printf("%d\n", sum[rt]);return MAX[rt];}PushDown(rt , r - l + 1);int m = (l + r) >> 1;int ret = -INF;if (L <= m) ret = max(ret, queryMAX(L , R , lson));if (m < R) ret = max(ret,queryMAX(L , R , rson));return ret;
}
int main() {int n , m;char str[5];while(scanf("%d%d",&n,&m)) {build(1 , n , 1);while (m--) {scanf("%s",str);int a , b , c;if(str[0]=='T') {scanf("%d%d%d",&a,&b,&c);update(a , b , c , 1 , n , 1);} else if(str[0]=='Q') {scanf("%d%d",&a,&b);cout<<querySUM(a,b,1,n,1)<<endl;} else if(str[0]=='A') {scanf("%d%d",&a,&b);cout<<queryMAX(a,b,1,n,1)<<endl;} else if(str[0]=='I') {scanf("%d%d",&a,&b);cout<<queryMIN(a,b,1,n,1)<<endl;}}}return 0;
}
//区间增加，区间查询#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 100100;
const int INF=0x7fffffff;
using namespace std;
int lazy[maxn<<2];
int SUM[maxn<<2],MAX[maxn<<2],MIN[maxn<<2];
void putup(int rt) {SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];MAX[rt] =max(MAX[rt<<1],MAX[rt<<1|1]) ;MIN[rt] =min(MIN[rt<<1],MIN[rt<<1|1]);
}
void putdown(int rt,int m) {if (lazy[rt]) {lazy[rt<<1] += lazy[rt];lazy[rt<<1|1] += lazy[rt];SUM[rt<<1] += lazy[rt] * (m - (m >> 1));SUM[rt<<1|1] += lazy[rt] * (m >> 1);MAX[rt<<1]+=lazy[rt];MAX[rt<<1|1] +=lazy[rt];MIN[rt<<1]+=lazy[rt];MIN[rt<<1|1]+=lazy[rt];lazy[rt] = 0;}
}
//以下的 l,r,rt 都带入 1,n,1
void build(int l,int r,int rt) { //初始化建树lazy[rt] = 0;if (l == r) {//初始化树为0的写法SUM[rt]=MAX[rt]=MIN[rt]=0;/* //边读入边建树的写法scanf("%d",&SUM[rt]);MAX[rt]=MIN[rt]=SUM[rt];*/return ;}int m = (l + r) >> 1;build(lson);build(rson);putup(rt);
}
void update(int L,int R,int v,int l,int r,int rt) { //将区间L~R的值增加vif (L <= l && r <= R) {lazy[rt] += v;SUM[rt] += v * (r - l + 1);MAX[rt]+=v;MIN[rt]+=v;return ;}putdown(rt , r - l + 1);int m = (l + r) >> 1;if (L <= m) update(L , R , v , lson);if (m < R) update(L , R , v , rson);putup(rt);
}
int querySUM(int L,int R,int l,int r,int rt) { //求区间L~R的和if (L <= l && r <= R) {return SUM[rt];}putdown(rt , r - l + 1);int m = (l + r) >> 1;int ret = 0;if (L <= m) ret += querySUM(L , R , lson);if (m < R) ret += querySUM(L , R , rson);return ret;
}
int queryMAX(int L,int R,int l,int r,int rt) { //求区间L~R的最大值if (L <= l && r <= R) {return MAX[rt];}putdown(rt , r - l + 1);int m = (l + r) >> 1;int ret = -INF;if (L <= m) ret =max(ret,queryMAX(L , R , lson)) ;if (m < R) ret =max(ret,queryMAX(L , R , rson)) ;return ret;
}
int queryMIN(int L,int R,int l,int r,int rt) { //求区间L~R的最小值if (L <= l && r <= R) {return MIN[rt];}putdown(rt , r - l + 1);int m = (l + r) >> 1;int ret = INF;if (L <= m) ret = min(ret,queryMIN(L , R , lson));if (m < R) ret = min(ret,queryMIN(L , R , rson));return ret;
}
int main() {int n , m;int a , b , c;char str[5];scanf("%d%d",&n,&m);build(1 , n , 1);while (m--) {scanf("%s",str);if (str[0] == 'S') {scanf("%d%d",&a,&b);printf("%d\n",querySUM(a , b , 1 , n , 1));} else if(str[0]=='C') {scanf("%d%d%d",&a,&b,&c);update(a , b , c , 1 , n , 1);} else if(str[0]=='A') {scanf("%d%d",&a,&b);printf("%d\n",queryMAX(a , b , 1 , n , 1));} else if(str[0]=='I') {scanf("%d%d",&a,&b);printf("%d\n",queryMIN(a , b , 1 , n , 1));}}return 0;
}