Altina's Interval Collection

Altina is curating an interval collection. A pair of positive integers \(l < r\) forms an interval \([l, r]\) with length \(r-l\). An interval \([l, r]\) is said to contain an interval \([x, y]\) if and only if \(l \le x\) and \(y \le r\); in particular, every interval contains itself.

For a nonempty set \(S\) of intervals:

• The maximum common subinterval is defined as the longest interval that is contained in every interval of \(S\). Formally, if \(S = \{[l_i,r_i]\}\), the candidate common interval is \([L, R]\) where \(L = \max_i\,l_i\) and \(R = \min_i\,r_i\). This interval is valid (i.e. defined) if and only if \(L < R\). Otherwise it is undefined.
• The minimum common superinterval is the shortest interval that contains every interval in \(S\). It is given by \([l_{\min}, r_{\max}]\) where \(l_{\min} = \min_i\,l_i\) and \(r_{\max} = \max_i\,r_i\), and its length is \(r_{\max} - l_{\min}\). Such an interval always exists.

Initially, Altina’s collection is empty. Then, there are \(Q\) events that modify her collection. Each event is one of the following:

1. Add an interval \([l, r]\) to the collection. (If the interval already exists, count it as a separate instance.)
2. Remove an existing interval \([l, r]\) from the collection. (If there are multiple copies, remove exactly one.)

After each event, Altina will select a nonempty subset \(S\) of her current collection according to the following rules:

1. If there exists any nonempty subset \(S\) whose maximum common subinterval is undefined (i.e. \(\max_i\,l_i \ge \min_i\,r_i\)), she will choose one of those.
2. If no such subset exists (i.e. every nonempty \(S\) has a defined maximum common subinterval), she will choose the subset for which the length of the maximum common subinterval, \(\min_i\,r_i - \max_i\,l_i\), is minimized.
3. Among the subsets satisfying the above condition, she picks one with the minimum common superinterval having the smallest length, i.e. \(r_{\max} - l_{\min}\) is minimized.

Your task is: after each event, output the length of the minimum common superinterval of the subset \(S\) chosen by Altina.

Note: For any nonempty subset \(S\) of intervals, when \(S\) is a pair \([l_1, r_1]\) and \([l_2, r_2]\), the maximum common subinterval is \([\max(l_1, l_2), \min(r_1, r_2)]\) (if \(\max(l_1, l_2) < \min(r_1, r_2)\)); otherwise it is undefined. Also, the minimum common superinterval of \(S\) is \([\min(l_1, l_2), \max(r_1, r_2)]\) with length \(\max(r_1, r_2)-\min(l_1, l_2)\). It turns out that an optimal choice is always achieved by selecting either a single interval or a pair of intervals from the collection.

inputFormat

The first line contains an integer \(Q\) (the number of events). Each of the next \(Q\) lines contains an event in one of the following formats:

• “+ l r”: Add the interval \([l, r]\) to the collection (\(l < r\)).
• “- l r”: Remove one instance of the interval \([l, r]\) from the collection. It is guaranteed that the interval exists at the time of removal.

outputFormat

After each event, output a single line containing one integer — the length of the minimum common superinterval of the subset \(S\) chosen by Altina, according to the rules described above.

sample

5
+ 1 3
+ 2 4
+ 3 5
- 2 4
- 1 3

2
2
4
4
2