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

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

Lid，将编号为id的书放在书架现在最左边那本书的左边。

Rid，将编号为id的书放在书架现在最右边那本书的右边。

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

【输入格式】

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

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

【输出格式】

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

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

1
1
2