题目描述

译自 CCO 2020 Day2 T2「Interval Collection」，翻译者：PinkRabbit。

Altina 正进行区间收藏。一对满足 $l < r$ 的正整数 $[l, r]$ 为一个区间，我们称这样的区间的长度为 $r - l$。

我们称区间 $[l, r]$ 包含区间 $[x, y]$，当且仅当 $l \le x$ 并且 $y \le r$。特别地，每个区间都包含自身。

定义一个非空集合 $S$ 的最大公共子区间为被 $S$ 中每个区间都包含的区间中最长的那个，如果没有这样的区间则未定义。

定义一个非空集合 $S$ 的最小公共超区间为包含 $S$ 中每个区间的区间中最短的那个，注意这样的区间总是存在。

初始时，Altina 的收藏中没有任何区间。接下来会发生 $Q$ 个事件，对 Altina 的收藏产生改变。

1. Altina 往她的收藏中添加一个区间 $[l, r]$，如果此时收藏中已有 $[l, r]$，应该被算作不同的两个区间。
2. Altina 移除一个在收藏中已经存在的区间 $[l, r]$，如有多个只以移除恰好一个。

在每个事件发生后，Altina 选择一个她的收藏中的非空子集 $S$，并且满足如下条件：

• 在所有的选取方案中，她会选择最大公共子区间未定义的。如果不存在这样的方案，则她会选择最大公共子区间的长度最小的。
• 在所有的满足上述条件的集合 $S$ 中，她会选择最小公共超区间的长度最小的。

请你在每一个事件发生后，输出 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

输入格式

第一行一个正整数 $Q$，表示将会发生的事件的个数。
接下来 $Q$ 行，每行描述一个事件，格式如下：

• $\mathtt{A}\;l\;r$：添加一个区间 $[l, r]$ 到 Altina 的收藏中。
• $\mathtt{R}\;l\;r$：从 Altina 的收藏中移除一个区间 $[l, r]$，保证这个区间在她的收藏中存在，且移除后她的收藏非空。

输出格式

输出 $Q$ 行，每行一个正整数表示每个事件发生后 Altina 会选择的集合 $S$ 的最小公共超区间的长度。

5
A 1 5
A 2 7
A 4 6
A 6 8
R 4 6

4
6
5
4
7

数据范围与提示

对于所有数据，保证 $1 \le Q \le 5 \times {10}^5$，$1 \le l < r \le {10}^6$。