你有一个书架,想在上面放一些书。
您将获得三种类型的 $$$q$$$ 查询:
1. L $$$id$$$ — 将索引为 $$$id$$$ 的书放在最左边现有书左侧的书架上;
2. R $$$id$$$ — 将索引为 $$$id$$$ 的书放在最右边现有书右侧的书架上;
3. ? $$$id$$$ — 计算需要从左侧或右侧弹出的最少书籍数量,以使索引为 $$$id$$$ 的书籍位于最左边或最右边。
您可以假设您要放置的第一本书可以有任何位置(这并不重要),并且 $$$3$$$ 类型的查询始终有效(保证每个此类查询中的书都已放置)。您还可以假设您不会将同一本书放在书架上两次,因此 $$$id$$$ 在前两种类型的查询中不会重复。
您的问题是回答 $$$3$$$ 类型的所有查询,以便它们出现在输入中。
请注意,在回答 $$$3$$$ 类型的查询后,所有书籍仍保留在书架上,并且书籍的相对顺序不会改变。
如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
然后是 $$$q$$$ 行。第 $$$i$$$ 行包含第 $$$i$$$ 查询,其格式与问题陈述中相同。保证查询始终有效(对于查询类型$$$3$$$,保证每个此类查询中的书已经放置过,对于其他类型,保证之前没有放置过该书)。
保证输入中至少有一个 $$$3$$$ 类型的查询。
在每个查询中,满足约束 $$$1 \le id \le 2 \cdot 10^5$$$。
输出
按 $$$3$$$ 类型查询的出现在输入中的顺序打印答案。
示例
输入 #1
8 L 1 R 2 R 3 ? 2 L 4 ? 1 L 5 ? 1
输出 #1
1 1 2
输入 #2
10 L 100 R 100000 R 123 L 101 ? 123 L 10 R 115 ? 100 R 110 ? 115
输出 #2
0 2 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$$$。
让我们看一下第二个示例并考虑查询:
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$$$。