题目描述

你有一个书架，然后你现在把书放上去。

你总共要操作 $q$ 次，操作有三类：

• L id，将编号为 id 的书放在书架现在最左边那本书的左边
• R id，将编号为 id 的书放在书架现在最右边那本书的右边。
• ? id，问你需要至少拿走几本书使得编号为 id 的书成为书架上最左边或者最右边那本书。

输入格式

输入的第一行包含一个整数 $q$ $（1≤q≤2×10^6）$。

然后有 $q$ 行，每一行为一个操作，格式见题面。数据保证至少有一个 ? 操作。$（1≤id≤2×10^6）$

输出格式

对于每一个 ? 操作，输出它的答案，一个操作输出一行。

8 
L 1 
R 2 
R 3 
? 2 
L 4 
? 1 
L 5 
? 1

1 
1 
2