应LJ号召开始做noi题,自然从最水的开始,裸的treap

//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read4.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
/////////////////////graph///////////////////////////////
#ifdef graphv
const int maxn=,maxm=;
struct GRAPH
{
    int next[maxm],first[maxn],to[maxm],value[maxm],cnt;
    void addedge(int x,int y,int z){next[++cnt]=first[x];first[x]=cnt;to[cnt]=y;value[cnt]=z;}
    void addedge2(int x,int y,int z){addedge(x,y,z);addedge(y,x,z);}
    void addedge2(int x,int y,int z,int xx){addedge(x,y,z);addedge(y,x,xx);}
};
#endif
#ifdef graphnv
const int maxn=,maxm=;
struct GRAPH
{
    int next[maxm],first[maxn],to[maxm],cnt;
    void addedge(int x,int y){next[++cnt]=first[x];first[x]=cnt;to[cnt]=y;}
    void addedge2(int x,int y){addedge(x,y);addedge(y,x);}
};
#endif
/////////////////variables&functions////////////////////
const int maxn=111111;
int n,minn,aha,tot;
char ch;
struct TREAP
{
    struct node
    {
        int l,r,data,key,size;
    }t[maxn];
    int root,num;
    void update(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+1;}
    pairs split(int a,int n)
    {
        if (n==0) return mp(0,a);
        int l=t[a].l,r=t[a].r;
        if (n==t[l].size) 
        {
            t[a].l=0;
            update(a);
            return mp(l,a);
        }
        else if (n==t[l].size+1)
        {
            t[a].r=0;
            update(a);
            return mp(a,r);
        }
        else if (n<t[l].size)
        {
            pairs tmp=split(l,n);
            t[a].l=tmp.second;
            update(a);
            return mp(tmp.first,a);
        }
        pairs tmp=split(r,n-t[l].size-1);
        t[a].r=tmp.first;
        update(a);
        return mp(a,tmp.second);
    }
    int merge(int a,int b)
    {
        if (a==0||b==0) return a+b;
        if (t[a].key<t[b].key)
        {
            t[a].r=merge(t[a].r,b);
            update(a);
            return a;
        }
        else
        {
            t[b].l=merge(a,t[b].l);
            update(b);
            return b;
        }
    }
    int rank(int x,int k)
    {
        int ans=0,tmp=inf;
        while (k)
        {
            if (x==t[k].data) tmp=min(tmp,ans+t[t[k].l].size+1);
            if (x>t[k].data) ans+=t[t[k].l].size+1,k=t[k].r;
            else k=t[k].l;
        }
        return tmp==inf?ans:tmp;
    }
    int rankk(int x,int k)
    {
        int ans=0,tmp=inf;
        while (k)
        {
            if (x==t[k].data) tmp=min(tmp,ans+t[t[k].l].size+1);
            if (x>t[k].data) ans+=t[t[k].l].size+1,k=t[k].r;
            else k=t[k].l;
        }
        return tmp;
    }
    int rank(int x){return rankk(x,root);}
    int find(int x,int k)
    {
        if (x>size()||x==0) return inf;
        while (1)
        {
            //if (!t[k].l&&x==1) return t[k].data;
            if (t[t[k].l].size==x-1) return t[k].data;
            if (t[t[k].l].size>x-1) k=t[k].l;
            else x=x-t[t[k].l].size-1,k=t[k].r;
        }
    }
    int find(int x){return find(x,root);}
    int pre(int x,int k)
    {
        int ans=-inf;
        while (k)
        {
            if (t[k].data<x) ans=max(ans,t[k].data),k=t[k].r;
            else k=t[k].l;
        }
        return ans;
    }
    int pre(int x){return pre(x,root);}
    int neg(int x,int k)
    {
        int ans=inf;
        while (k)
        {
            if (t[k].data>x) ans=min(ans,t[k].data),k=t[k].l;
            else k=t[k].r;
        }
        return ans;
    }
    int neg(int x){return neg(x,root);}
    void insert(int x)
    {
        int k=rank(x,root);
        pairs tmp=split(root,k);
        t[++num].data=x;
        t[num].key=(int)(rand()*rand());
        t[num].size=1;
        root=merge(tmp.first,num);
        root=merge(root,tmp.second);
    }
    int erase(int x)
    {
        int k=rankk(x,root);
        if (k==inf) return -1;
        int res=t[k].data;
        pairs t1=split(root,k),t2=split(t1.first,k-1);
        root=merge(t2.first,t1.second);
        return res;
    }
    void erase_lower(int x,int k,int fa)
    {
        if (!k) return;
        if (t[k].data>=x) {erase_lower(x,t[k].l,k);update(k);}
        else 
        {
            int temp;
            if (fa==-1) {tot+=t[t[k].l].size+1;root=t[k].r;temp=t[k].r;t[k].r=0;}
            else
            {
                tot+=t[t[k].l].size+1;
                temp=t[k].r;
                t[k].r=0;//split now and now.r
                t[fa].l=temp;//merge r and fa
            }
            if (temp) 
            {
                erase_lower(x,temp,fa);
                update(temp);
            }
        }
    }
    void erase_lower(int x){erase_lower(x,root,-1);}
    int size(){return t[root].size;}
}T;
int main()
{
    read(n,minn);
    rep(i,1,n)
    {
        ch=getchar();
        int x;
        read(x);
        if (ch=='I'){if (x>=minn+aha) T.insert(x-aha);}//min+aha == minwhenbegin;
        else if (ch=='F')
        {
            printf("%d\n",T.size()>=x?(T.find(T.size()-x+1)+aha):-1);
        }
        else if (ch=='A'){minn-=x;aha+=x;}
        else//S 
        {
            minn+=x;
            aha-=x;
            //T ones whose data<min
            T.erase_lower(minn);
        }
    }
    printf("%d\n",tot);
    return 0;
}