队列，$map$。

每次出队进行出队操作的是时候，先把队列中需要出队的人全部出队，然后比较对头和当前出队的人是否相同。

#include
     
      using namespace std;int T,n,sz,sum;int f[100010];char op[100];int main(){    scanf("%d",&T);    while(T--)    {        scanf("%d",&n); sum=sz=0;        map
      
       zhuan;        queue
       
        Q;        memset(f,0,sizeof f);        for(int i=1;i<=n;i++)        {            scanf("%s",op);            if(op[0]=='i')            {                scanf("%s",op);                zhuan[op]=++sz;                Q.push(sz);            }            else            {                while(1)                {                    if(Q.empty()) break;                    if(f[Q.front()]==0) break;                    Q.pop();                }                scanf("%s",op);                int id = zhuan[op];                f[id]=1;                if(Q.front()!=id) sum++;            }        }        printf("%d\n",n/2-sum);    }    return 0;}