Keep In Line

又到饭点了，SK同学靠着惯性走到了食堂，但长长的队伍顿时让他失去了食欲。突然，他注意到某个窗口前的队伍里明显存在插队的现象，于是他默默记录下了同学们进队和出队的变化。 ? ?
对于进队，SK同学只知道队伍里多了一个人，并不知道新来的人是老老实实站到了队尾还是插到了队伍里的某个位置；对于出队，SK同学能确定是队伍里站在最前面的人出队了。
初始时队伍为空，给出 n 条队伍进出的信息，保证已经出队的同学不会再入队，并且最终队伍也为空，现在SK同学想知道有多少不插队的好同学。

输入
第一行是一个正整数 T (T ≤ 5)，表示测试数据的组数.
对于每组测试数据， 第一行是一个整数 n (1≤ n ≤ 100000)，表示这个队伍进出的信息数.
?接下来 n 行，每行是两个字符串 Opt Name，其中 Opt 为 "in" 代表进队，"out" 代表出队，Name 为进队或出队的人的名字， 所有信息按照时间顺序给出，名字由英文字母和阿拉伯数字组成，长度不超过 10，保证每个人的名字各不相同。

输出
对于每组测试数据，输出一行，包含一个整数，表示不插队的人数。

Input
1
6
in quailty
in hwq1352249
out hwq1352249
in zhuaiballl
out quailty
out zhuaiballl

Output
2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int t;
int n;
string s,p;
queue <int> q;
int cnt;
map <string,int> k;
bool vis[N];
int get(string s)
{
    if (k.count(s)==0) k[s]=++cnt;
    return k[s];
}
signed main()
{
    ios;
    cin>>t;
    while (t--)
    {
        cin>>n;
        cnt=0;
        k.clear();
        int sum=0;
        memset(vis,0,sizeof vis);
        while (n--)
        {
            cin>>s>>p;
            int x=get(p);
            if (s=="in") q.push(x);
            else 
            {
                if (q.front()==x)
                {
                    sum++;
                    q.pop();
                }
                else 
                {
                    vis[x]=1;
                }
            }
            while (q.size()&&vis[q.front()]) 
            {
                q.pop();
            }
        }
        cout<<sum<<endl;
    }
}