题目背景

本题题面来自 LOJ。

题目描述

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,5]$，选择 $[1,5]$ 最优，答案为 $4$。

加入 $[2,7]$，选择 $[1,5],[2,7]$ 最优，答案为 $7-1=6$。

加入 $[4,6]$，选择 $[1,5],[4,6]$ 最优，答案为 $6-1=5$。

加入 $[6,8]$，选择 $[4,6],[6,8]$ 最优，答案为 $8-4=4$。

删除 $[4,6]$，选择 $[1,5],[6,8]$ 最优，答案为 $8-1=7$。

子任务

本题使用捆绑测试

• Subtask 1（$12$ 分）：$Q\le 500$。
• Subtask 2（$32$ 分）：$Q\le 1.2\times 10^4$。
• Subtask 3（$28$ 分）：$Q\le 5\times 10^4$。
• Subtask 4（$16$ 分）：对于任两个区间 $(l_1,r_1)$ 和 $(l_2,r_2)$，保证 $r_1<l_2$ 或者 $r_2<l_1$。
• Subtask 5（$12$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le Q\le 5\times 10^5$，$1\le l,r\le 10^6$。

说明

本题译自 Canadian Computing Olympiad 2020 Day 2 T2 Interval Collection。

本题数据有所删减。