e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Similar numbers

Similar numbers

In developing the system of data analysis needed to solve the following particular problem. There is a set of integers (initially empty) and a sequence of queries of three types:

  • ADD xadd an element x in the set (if an element already exists, then the set does not change)
  • DEL xdelete element x from the set (if no such element, then the set does not change)
  • FINDfind and display the distance between the two closest elements in the set. This ensures that the set has at least two elements.

Required to fulfill a given sequence of requests.

Input

The first line contains one integerN (1 <= N <= 100 000) — total number of requests. In each of the nextNlines of a written request pursuant to the above format. All numeric values in the query are in the range from1 to 1 000 000 000.

Output

Bring one number in the row for each query typeFINDthe distance between the two closest elements in the set at the time of the query.

Time limit 3 seconds
Memory limit 64 MiB
Input example #1
7
ADD 1
ADD 5
ADD 4
ADD 6
FIND
DEL 5
FIND
Output example #1
1
2
Author Igor Andrianov