暂无测试数据。

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

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

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

输入格式

输入的第一行包含一个整数 $q$（$1\le q\le 2 \times 10^{5}$）。

然后有 $q$ 行，每一行为一个操作，格式见题面。数据保证至少有一个 $?$ 操作。（$1\le id\le 2 \times 10^{5}$）

输出格式

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

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

1
1
2

10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115

0
2
1