SOLVE
LATER
This task is really interesting so authors even decided not to spend your time on reading the statement!
Initially you have a straight line without any points on it and you need to perform three types of queries:
1 x - add a point with an integer coordinate x. Guaranteed that there is no such point before running this query.
2 x - delete a point with an integer coordinate x. Guaranteed that this point exists before running this query.
3 x - define a coordinate of i-th existing point in increasing order as \(x_i\) and number of existing points as n. You need to find \(max ( \sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}| )\) for all permutations p of length n where \(x_{p_1}=x\). Guaranteed that this point exists before running this query.
Input
The first line of input contains a single integer q \((1 \leq q \leq 100 000)\) - the number of queries.
Then follow q lines. The i-th of these lines contains two integers \(type_i\) and \(x_i\) \((1 \leq type_i \leq 3, 0 \leq x_i \leq 10^{9})\).
Output
For each query of the third type print the maximum value.
Permutation for the first ask query is {3, 1, 4, 2}. It's value is 11.
Permutation for the second ask query is {3, 1, 2}. It's value is 7.