CF1066C.Books Queries

You have got a shelf and want to put some books on it.

You are given $q$ queries of three types:

1. L $id$ — put a book having index $id$ on the shelf to the left from the leftmost existing book;
2. R $id$ — put a book having index $id$ on the shelf to the right from the rightmost existing book;
3. ? $id$ — calculate the minimum number of books you need to pop from the left or from the right in such a way that the book with index $id$ will be leftmost or rightmost.

You can assume that the first book you will put can have any position (it does not matter) and queries of type $3$ are always valid (it is guaranteed that the book in each such query is already placed). You can also assume that you don't put the same book on the shelf twice, so $id$s don't repeat in queries of first two types.

Your problem is to answer all the queries of type $3$ in order they appear in the input.

Note that after answering the query of type $3$ all the books remain on the shelf and the relative order of books does not change.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

你有一个书架，想要在上面放置一些书。

你将收到 $q$ 个查询，共三种类型：

1. L $id$ — 将编号为 $id$ 的书放在当前最左侧已有书籍的左侧；
2. R $id$ — 将编号为 $id$ 的书放在当前最右侧已有书籍的右侧；
3. ? $id$ — 计算最少需要从左侧或右侧移除多少本书，才能使编号为 $id$ 的书成为最左侧或最右侧的书。

你可以假设：第一次放置的书可以位于任意位置（这无关紧要）；类型 $3$ 的查询总是合法的（即保证每次此类查询中指定的书已经放置在书架上）。此外，你不会将同一本书重复放置到书架上，因此前两类查询中的 $id$ 不会重复。

你的任务是按输入中出现的顺序回答所有类型 $3$ 的查询。

注意：在回答完一个类型 $3$ 的查询后，所有书仍保留在书架上，且书的相对顺序不变。

如果你使用 Python 编程，请在提交代码时考虑使用 PyPy 而非 Python。

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow. The $i$-th line contains the $i$-th query in format as in the problem statement. It is guaranteed that queries are always valid (for query type $3$, it is guaranteed that the book in each such query is already placed, and for other types, it is guaranteed that the book was not placed before).

It is guaranteed that there is at least one query of type $3$ in the input.

In each query the constraint $1 \le id \le 2 \cdot 10^5$ is met.

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示查询的数量。

接下来是 $q$ 行，第 $i$ 行包含第 $i$ 个查询，其格式与题目描述中一致。保证所有查询均有效（对于类型为 $3$ 的查询，保证每次查询所涉及的书本均已放置；对于其他类型的查询，保证所涉及的书本此前未被放置）。

保证输入中至少存在一个类型为 $3$ 的查询。

在每个查询中，约束条件 $1 \le id \le 2 \cdot 10^5$ 均成立。

Print answers to queries of the type $3$ in order they appear in the input.

按输入中出现的顺序输出类型为 $3$ 的查询的答案。

Let's take a look at the first example and let's consider queries:

1. The shelf will look like $[1]$;
2. The shelf will look like $[1, 2]$;
3. The shelf will look like $[1, 2, 3]$;
4. The shelf looks like $[1, \textbf{2}, 3]$ so the answer is $1$;
5. The shelf will look like $[4, 1, 2, 3]$;
6. The shelf looks like $[4, \textbf{1}, 2, 3]$ so the answer is $1$;
7. The shelf will look like $[5, 4, 1, 2, 3]$;
8. The shelf looks like $[5, 4, \textbf{1}, 2, 3]$ so the answer is $2$.

Let's take a look at the second example and let's consider queries:

1. The shelf will look like $[100]$;
2. The shelf will look like $[100, 100000]$;
3. The shelf will look like $[100, 100000, 123]$;
4. The shelf will look like $[101, 100, 100000, 123]$;
5. The shelf looks like $[101, 100, 100000, \textbf{123}]$ so the answer is $0$;
6. The shelf will look like $[10, 101, 100, 100000, 123]$;
7. The shelf will look like $[10, 101, 100, 100000, 123, 115]$;
8. The shelf looks like $[10, 101, \textbf{100}, 100000, 123, 115]$ so the answer is $2$;
9. The shelf will look like $[10, 101, 100, 100000, 123, 115, 110]$;
10. The shelf looks like $[10, 101, 100, 100000, 123, \textbf{115}, 110]$ so the answer is $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$。