Points on line
Tag(s):

## Data Structures, Medium-Hard

Problem
Editorial
Analytics

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.

SAMPLE INPUT
7
1 0
1 5
1 4
1 3
3 4
2 5
3 4

SAMPLE OUTPUT
11
7

Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Bit Manipulation
• Algorithms > Dynamic Programming
• Algorithms > Sorting
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Graphs
• Math > Linear Algebra
• Algorithms > Searching
• Algorithms > Dynamic Programming