## 题解 P1503 【鬼子进村】

#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 123456
using namespace std;

IL void of(R II &a) {
R char c=getchar(); R II w=1,p=0;
while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar(); }
while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar(); }
a=p*w;
}

/* -------------------- Peipei -------------------- */

II block,n,m,_top;

IL II Ll(R II x) {
R II ans=0;
while (x>0 && !lazy[x/block]) ans+=min(x,block), x-=block;
while (x>0 && !had[x]) ans++, x--;
return ans;
}

IL II Rr(R II x) {
R II ans=0; if(x==n+1) return 0;
while (x<=n && !lazy[belong[x]]) ans+=block, x+=block;
if(x>n+1) ans-=block-(n-n/block*block);
while (x<=n && !had[x]) ans++, x++;
return ans;
}

IL II todo(R II x) {
R II ans=0,l=x,r=x,flag=0;
while (l && belong[l]==belong[x]) {
ans++; l--;
if(had[l]) { flag=1; break ; }
}
if(!flag) ans+=Ll(l);
flag=0;
r++;
while (r<=n && belong[r]==belong[x]) {
if(had[r]) { flag=1; break ; }
ans++; r++;
}
if(!flag) ans+=Rr(r);
return ans;
}

int main()
{
//    freopen("1.in","r",stdin);

of(n); of(m); block=sqrt(n);
for(R II i=1;i<=n;i++) belong[i]=(i-1)/block+1;
R char opt; R II x;
while (m --) {
cin>> opt;
if(opt=='D') {
of(x); Stack[++_top]=x;
lazy[belong[x]]++;
}
if(opt=='R') {
x=Stack[_top--];
lazy[belong[x]]--;
}
if(opt=='Q') {
of(x);
printf("%d\n",todo(x));
}
}
}