Interval Collection

Altina is starting an interval collection. An interval is a pair of positive integers $[l, r]$ with $l < r$. The length of the interval is $r - l$. An interval $[l, r]$ contains another interval $[x, y]$ if $l \le x$ and $y \le r$. Every interval contains itself.

For a non-empty set $S$ of intervals, the common intervals are all intervals $[x, y]$ that are contained in every interval $[l, r]$ in $S$. If the set of common intervals is non-empty, the greatest common interval of $S$ is the common interval with the largest length.

For the same set $S$, the enclosing intervals are all intervals $[x, y]$ that contain every interval $[l, r]$ in $S$. This set is always non-empty, so the least enclosing interval of $S$ is the enclosing interval with the smallest length.

Initially, Altina has no intervals. There are $Q$ events that change the intervals she owns.

The first type of event adds an interval $[l, r]$ to her collection. The same $[l, r]$ may be added more than once, and each copy is treated as a separate interval.

The second type of event removes an existing interval $[l, r]$ from her collection. If she has several intervals with the same $[l, r]$, she removes exactly one of them.

After each event, Altina chooses a non-empty subset $S$ of the intervals she owns. She first prefers a set with no greatest common interval, if one exists. If none exists, she picks a set whose greatest common interval has the smallest possible length. Among the sets that satisfy this condition, she picks one whose least enclosing interval has the smallest possible length.

Your task is to output the length of the least enclosing interval of the set $S$ she chose after each event.

The first line of input contains $Q$ ($1 \le Q \le 500\,000$), the total number of add and remove operations. The next $Q$ lines have one of the following forms:

• A $l$ $r$: add the interval $[l, r]$ to Altina's collection.
• R $l$ $r$: remove one copy of the interval $[l, r]$ from Altina's collection. The interval is guaranteed to exist, and the collection is guaranteed to be non-empty after the removal.

For all subtasks, $1 \le l < r \le 1\,000\,000$.

The output consists of $Q$ lines. Each line contains the length of the least enclosing interval of the set $S$ Altina chose after the corresponding event.

After $[1, 5]$ is added, the only valid choice is $S = \{[1, 5]\}$, and its least enclosing interval is $[1, 5]$.

After $[2, 7]$ is added, $S = \{[1, 5], [2, 7]\}$ has the greatest common interval $[2, 5]$ and the least enclosing interval $[1, 7]$.

After $[4, 6]$ is added, $S = \{[1, 5], [4, 6]\}$ has the greatest common interval $[4, 5]$ and the least enclosing interval $[1, 6]$.

After $[6, 8]$ is added, $S = \{[4, 6], [6, 8]\}$ has no greatest common interval, and its least enclosing interval is $[4, 8]$. The set $S = \{[1, 5], [6, 8]\}$ also has no greatest common interval, but its least enclosing interval $[1, 8]$ is longer than $[4, 8]$.

After $[4, 6]$ is removed, $S = \{[1, 5], [6, 8]\}$ has no greatest common interval, and its least enclosing interval is $[1, 8]$.