구간 모음

알티나는 구간 모음을 만들기 시작한다. 구간은 $l < r$을 만족하는 양의 정수 두 개 $[l, r]$이다. 구간의 길이는 $r - l$이다. 구간 $[l, r]$이 다른 구간 $[x, y]$를 포함한다는 것은 $l \le x$이고 $y \le r$이라는 뜻이다. 모든 구간은 자기 자신을 포함한다.

공집합이 아닌 구간 집합 $S$에 대해, 공통 구간은 $S$의 모든 구간 $[l, r]$에 포함되는 구간 $[x, y]$ 전체이다. 공통 구간 집합이 공집합이 아니면, $S$의 최대 공통 구간은 공통 구간 중 길이가 가장 긴 구간이다.

같은 $S$에 대해, 포괄 구간은 $S$의 모든 구간 $[l, r]$을 포함하는 구간 $[x, y]$ 전체이다. 이 집합은 항상 공집합이 아니므로, $S$의 최소 포괄 구간은 포괄 구간 중 길이가 가장 짧은 구간이다.

처음에 알티나의 모음은 비어 있다. 알티나가 가진 구간을 바꾸는 사건이 $Q$번 일어난다.

첫 번째 종류의 사건은 알티나의 모음에 구간 $[l, r]$을 추가한다. 같은 $[l, r]$을 여러 번 추가할 수 있으며, 각각은 서로 다른 구간으로 취급한다.

두 번째 종류의 사건은 모음에 있는 구간 $[l, r]$을 하나 제거한다. 같은 $[l, r]$이 여러 개 있으면 그중 정확히 하나만 제거한다.

사건이 일어날 때마다 알티나는 자신이 가진 구간 중에서 공집합이 아닌 부분집합 $S$를 고른다. 먼저 가능하다면 최대 공통 구간이 없는 $S$를 고른다. 그것이 불가능하면 최대 공통 구간의 길이가 가장 작은 $S$를 고른다. 이 조건을 만족하는 $S$ 중에서는 최소 포괄 구간의 길이가 가장 작은 것을 고른다.

각 사건 후 알티나가 고른 $S$의 최소 포괄 구간 길이를 구하라.

첫째 줄에 $Q$ ($1 \le Q \le 500\,000$)가 주어진다. 이는 추가와 제거 연산의 전체 개수이다. 다음 $Q$개의 줄은 아래 형식 중 하나이다.

• A $l$ $r$: 구간 $[l, r]$을 알티나의 모음에 추가한다.
• R $l$ $r$: 구간 $[l, r]$ 하나를 모음에서 제거한다. 제거할 구간은 반드시 존재하며, 제거한 뒤에도 모음은 공집합이 아니다.

모든 부분 문제에 대해 $1 \le l < r \le 1\,000\,000$이다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 사건 후 알티나가 고른 $S$의 최소 포괄 구간 길이를 출력한다.

$[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]$이다.