Description

Altina is collecting intervals. A pair of positive integers $[l, r]$ with $l < r$ is an interval, and we call the length of such an interval $r - l$.

We say that interval $[l, r]$ contains interval $[x, y]$ if and only if $l \le x$ and $y \le r$. In particular, every interval contains itself.

For a non-empty set $S$, define its maximum common sub-interval as the longest interval that is contained in every interval in $S$. If no such interval exists, it is undefined.

For a non-empty set $S$, define its minimum common super-interval as the shortest interval that contains every interval in $S$. Note that such an interval always exists.

Initially, there are no intervals in Altina’s collection. Then $Q$ events will happen, which change Altina’s collection.

1. Altina adds an interval $[l, r]$ to her collection. If $[l, r]$ already exists in the collection, it should be counted as a different interval.
2. Altina removes an interval $[l, r]$ that already exists in the collection. If there are multiple identical ones, remove exactly one.

After each event, Altina chooses a non-empty subset $S$ of her collection, satisfying the following rules:

• Among all choices, she will choose one where the maximum common sub-interval is undefined. If no such choice exists, she will choose one where the length of the maximum common sub-interval is as small as possible.
• Among all sets $S$ that satisfy the rule above, she will choose one where the length of the minimum common super-interval is as small as possible.

After each event, output the length of the minimum common super-interval of the set $S$ that Altina will choose.

Input Format

The first line contains a positive integer $Q$, the number of events.
The next $Q$ lines each describe an event in one of the following formats:

• $\mathtt{A}\;l\;r$: add an interval $[l, r]$ to Altina’s collection.
• $\mathtt{R}\;l\;r$: remove an interval $[l, r]$ from Altina’s collection. It is guaranteed that this interval exists in her collection, and that after removal her collection is non-empty.

Output Format

Output $Q$ lines. Each line contains one positive integer, the length of the minimum common super-interval of the set $S$ that Altina will choose after that event.

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

4
6
5
4
7

Hint

Sample Explanation

Add $[1,5]$. Choosing $[1,5]$ is optimal, so the answer is $4$.

Add $[2,7]$. Choosing $[1,5],[2,7]$ is optimal, so the answer is $7-1=6$.

Add $[4,6]$. Choosing $[1,5],[4,6]$ is optimal, so the answer is $6-1=5$.

Add $[6,8]$. Choosing $[4,6],[6,8]$ is optimal, so the answer is $8-4=4$.

Remove $[4,6]$. Choosing $[1,5],[6,8]$ is optimal, so the answer is $8-1=7$.

Subtasks

This problem uses bundled testdata.

• Subtask 1 ($12$ points): $Q\le 500$.
• Subtask 2 ($32$ points): $Q\le 1.2\times 10^4$.
• Subtask 3 ($28$ points): $Q\le 5\times 10^4$.
• Subtask 4 ($16$ points): For any two intervals $(l_1,r_1)$ and $(l_2,r_2)$, it is guaranteed that $r_1<l_2$ or $r_2<l_1$.
• Subtask 5 ($12$ points): No special restrictions.

For $100\%$ of the data, it is guaranteed that $1\le Q\le 5\times 10^5$ and $1\le l,r\le 10^6$.

Notes

This problem is translated from Canadian Computing Olympiad 2020 Day 2 T2 Interval Collection.

Translated by ChatGPT 5