#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 2000005
int n,a,b,l[N],t[N],r[N],cnt,k[N];char s[22];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s>>a;
		if(s[1]=='u'){
			cin>>b,k[a]++;if(k[a]==1) l[a+n]=r[a+n]=a+n;
			if(s[5]=='f') t[++cnt]=b,r[cnt]=r[a+n],l[r[a+n]]=cnt,r[a+n]=cnt,l[cnt]=a+n;
			else t[++cnt]=b,l[cnt]=l[a+n],r[l[a+n]]=cnt,l[a+n]=cnt,r[cnt]=a+n;
		}else{
			if(!k[a]) continue;
			if(s[0]=='p'){
				if(s[4]=='f') l[r[r[a+n]]]=a+n,r[a+n]=r[r[a+n]],k[a]--;
				else r[l[l[a+n]]]=a+n,l[a+n]=l[l[a+n]],k[a]--;
			}else if(s[0]=='s') cout<<k[a]<<endl;
			else if(s[0]=='f') cout<<t[r[a+n]]<<endl;
			else cout<<t[l[a+n]]<<endl;
		}
	}
	return 0;
}