题目描述

译自 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$ 的最小公共超区间的长度。

样例

input

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

output

4
6
5
4
7

当 $[1, 5]$ 被加入后，只有一个区间。所以 $S = {[1, 5]}$ 是唯一的选择，最小公共超区间为 $[1, 5]$。

当 $[2, 7]$ 被加入后，$S = {[1, 5], [2, 7]}$，最大公共子区间为 $[2, 5]$，最小公共超区间为 $[1, 7]$。

当 $[4, 6]$ 被加入后，$S = {[1, 5], [4, 6]}$，最大公共子区间为 $[4, 5]$，最小公共超区间为 $[1, 6]$。

当 $[6, 8]$ 被加入后，$S = {[4, 6], [6, 8]}$，最大公共子区间不存在，最小公共超区间为 $[4, 8]$。注意到 $S = {[1, 5], [6, 8]}$ 也不存在最大公共子区间，但是它的最小公共超区间为 $[1, 8]$，长度比 $[4, 8]$ 要更长。

当 $[4, 6]$ 被移除后，$S = {[1, 5], [6, 8]}$，最大公共子区间不存在，最小公共超区间为 $[1, 8]$。

数据范围与提示

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