CF1066C Books Queries

你有一个书架，想在上面放些书。 共有 $q$ 次操作，分为三种类型： 1. L $id$ - 将编号为 $id$ 的书放到书架上现有的最靠左的书的左边； 2. R $id$ - 将编号为 $id$ 的书放到书架上现有的最靠右的书的右边； 3. ? $id$ - 计算最少需要从左边或右边取下多少本书，才能使编号为 $id$ 的书处在最左边或最右边。 你可以假设，你要放入的第一本书可以放在任何位置（这并不重要），并且类型 $3$ 的操作总是有效的（可以保证每个此类操作中的书都已经放入）。你还可以假设同一本书不会被放在书架上两次，即前两种类型的操作中相同的 $id$ 不会重复出现。 你的任务是按照输入中出现的顺序回答所有类型 $3$ 的操作。 请注意，在回答了类型 $3$ 的操作后，所有的书仍然在书架上，书的相对顺序不会改变。 **Python 选手请考虑使用 PyPy 提交。**

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示操作次数。 接下来的 $q$ 行，第 $i$ 行包含第 $i$ 个操作，格式如题面所示。保证操作是有效的（对于类型 $3$ ，保证操作中的书已经被放在书架上，对于其他类型，保证操作中的书还未被放在书架上）。 保证输入中至少有一个操作类型为 $3$ 。 对于每次操作，$1 \le id \le 2 \cdot 10^5$。

按照输入中出现的顺序输出类型 $3$ 的操作的答案。

**【样例解释 #1】** 每次操作后书架的状态： 1. 书架状态为 $[1]$； 2. 书架状态为 $[1, 2]$； 3. 书架状态为 $[1, 2, 3]$； 4. 书架状态为 $[1, \textbf{2}, 3]$ ，所以答案是 $1$； 5. 书架状态为 $[4, 1, 2, 3]$； 6. 书架状态为 $[4, \textbf{1}, 2, 3]$ ，所以答案是 $1$； 7. 书架状态为 $[5, 4, 1, 2, 3]$； 8. 书架状态为 $[5, 4, \textbf{1}, 2, 3]$，所以答案是 $2$。 **【样例解释 #2】** 每次操作后书架的状态： 1. 书架状态为 $[100]$； 2. 书架状态为 $[100, 100000]$； 3. 书架状态为 $[100, 100000, 123]$； 4. 书架状态为 $[101, 100, 100000, 123]$； 5. 书架状态为 $[101, 100, 100000, \textbf{123}]$，所以答案是 $0$； 6. 书架状态为 $[10, 101, 100, 100000, 123]$； 7. 书架状态为 $[10, 101, 100, 100000, 123, 115]$； 8. 书架状态为 $[10, 101, \textbf{100}, 100000, 123, 115]$，所以答案是 $2$； 9. 书架状态为 $[10, 101, 100, 100000, 123, 115, 110]$； 10. 书架状态为 $[10, 101, 100, 100000, 123, \textbf{115}, 110]$，所以答案是 $1$。