/*
Mail to : miyubai@gamil.com
Link : http://www.cnblogs.com/MiYu || http://m.shnenglu.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : 1540
Doc Name : Tunnel Warfare
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
inline int max ( int &a, int &b ) {
return a > b ? a : b;
}
struct segTree {
int left, right, lVal, rVal, mVal; //lVal: 從線段左端點(diǎn)能夠向右延伸的最大長度
//rVal: 從線段右端點(diǎn)能夠向左延伸的最大長度
//mVal: 當(dāng)前線段的最大連續(xù)長度
int mid () { return (left + right)>>1;}
int dis () { return right-left+1; } // 線段的長度
void prs (int flag) { lVal = rVal = mVal = flag ? 0 : dis(); } //按flag標(biāo)記處理線段
bool cov () { return mVal == dis(); } // 當(dāng)前線段是否被覆蓋 , 即 這條線段上的點(diǎn)沒有任何一點(diǎn)被破壞
}seg[160000];
inline void creat ( int left, int right, int rt = 1 ) {
int LL = rt << 1, RR = rt << 1 | 1;
seg[rt].left = left;
seg[rt].right = right;
seg[rt].prs (0);
if ( left == right ) return;
int mid = seg[rt].mid();
creat ( left, mid, LL );
creat ( mid + 1, right, RR );
}
inline void modify ( int pos, int flag, int rt = 1 ) {
int LL = rt << 1, RR = rt << 1 | 1;
if ( seg[rt].left == seg[rt].right ) {
seg[rt].prs ( flag ); return;
}
int mid = seg[rt].mid();
if ( pos <= mid ) modify ( pos, flag, LL );
else modify ( pos, flag, RR );
// 經(jīng)典部分:
seg[rt].mVal = max ( seg[LL].rVal + seg[RR].lVal, max ( seg[LL].mVal, seg[RR].mVal ) ); //當(dāng)前節(jié)點(diǎn)的最大連續(xù)長度
seg[rt].lVal = seg[LL].lVal + ( seg[LL].cov() ? seg[RR].lVal : 0 ); //當(dāng)前節(jié)點(diǎn)的左端點(diǎn)能夠向右延伸的最大長度
seg[rt].rVal = seg[RR].rVal + ( seg[RR].cov() ? seg[LL].rVal : 0 ); //當(dāng)前節(jié)點(diǎn)的右端點(diǎn)能夠向左延伸的最大長度
}
inline int query ( int pos, int rt = 1 ) {
if ( seg[rt].cov() || seg[rt].mVal == 0 || seg[rt].left == seg[rt].right )
return seg[rt].mVal;
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( pos <= mid ) {
if ( pos > mid - seg[LL].rVal ) // 查詢節(jié)點(diǎn)在左孩子節(jié)點(diǎn)所處的位置
return seg[LL].rVal + query ( mid+1, RR ); // 如果在線段的右端, 則還需要查詢右孩子節(jié)點(diǎn)的左端
else return query ( pos, LL ); //左端只需查詢左端
} else {
if ( pos <= mid + seg[RR].lVal ) // 同上
return seg[RR].lVal + query ( mid, LL );
else return query ( pos, RR );
}
}
inline int _getint(int &n){ //輸入加速
char c;for(c=getchar();!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())n=n*10+c-'0';return n;
}
deque <int> st; // stack 沒有clear() 杯具了
int main ()
{
int N, M;
char ask[3];
while ( scanf ( "%d%d", &N, &M ) == 2 ) {
creat ( 1, N );
st.clear();
while ( M -- ) {
scanf ( "%s",ask ); N = 0;
switch ( ask[0] ) {
case 'D': _getint (N);
modify ( N, 1 );
st.push_back ( N );
break;
case 'Q': _getint (N);
printf ( "%d\n",query ( N ) );
break;
case 'R': if ( st.empty() ) break;
modify ( st.back(), 0 );
st.pop_back();
}
}
}
return 0;
}