## TREAP - Yet another range difference query!

no tags

Given an empty set S, you have to apply Q operations on this set while keeping the set sorted in increasing order and elements have indices 0 <= i < size(S)

The operations are insert, delete, find min difference in a given range, find max difference in a given range.

### Input

I k
Insert k into S, if k is not in S
D k
Delete k from S, if k is in S
N i j
Print min{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element
X i j
Print max{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element

I k : Insert k into S, if k is not in S

D k : Delete k from S, if k is in S

N i j : Print min{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element

X i j : Print max{abs(S[x] - S[y]) | i <= x, y <= j} or -1 if the range has 1 element

limits: 0 < Q <= 200000 , 0 <= k <= 10^9 , 0 <= i,j < size(S)

### Output

For each N and X operations, print an integer per line as described above.

### Example

```Input:
11
I 1
I 12
I 4
I 8
N 0 3
X 0 3
N 1 3
X 0 2
D 4
N 0 1
X 1 2

Output:
3
11
4
7
7
4``` jusbut1943: 2018-08-31 11:16:01 Why my solution is black, and shows 0K, Result: 0. fz0718: 2017-07-22 23:10:28 Another fun BBST problem, that you also need lazy propagation for: https://csacademy.com/contest/archive/task/strings/ mahmud2690: 2016-05-25 13:30:54 Why my solution is black, and shows 0K, Result: 0. timonknigge: 2015-08-31 15:20:40 It might be worth pointing out that for the N query, we also require that x =/= y. bicsi: 2015-07-02 23:38:35 This was probably the most resourceful problem I have ever coded! However, it was worth it in the end! :D