← 返回题目列表

Codeforces · 1066/C

C. 图书查询

中文机器翻译题面 查看原题

你有一个书架,想在上面放一些书。

您将获得三种类型的 $$$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$$$。