При разработке системы
анализа данных потребовалось решить следующую частную задачу. Имеется множество
целых чисел (вначале пустое) и дана последовательность запросов трёх типов:
ADD x
— добавить элемент x во множество (если такой элемент
уже есть, то множество не изменяется)
DEL x
— удалить элемент x из множества (если такого
элемента нет, то множество не изменяется)
FIND — найти и вывести
расстояние между двумя самыми близкими элементами в
множестве. При этом гарантируется, что в множестве
имеется не менее двух элементов.
Требуется выполнить заданную
последовательность запросов.
Первая строка входного
файла содержит одно целое число N
(1 £ N £ 100 000) — общее количество
запросов. В каждой из следующих N
строк записан один запрос согласно приведённому выше формату. Все числовые
значения в запросах лежат в диапазоне от 1 до 1 000 000 000.
Выведите в выходной
файл по одному числу в строке для каждого запроса типа FIND —
расстояние между двумя наиболее близкими элементами в
множестве на момент выполнения запроса.
Пример
|
Входные данные
|
Выходные данные
|
|
7
ADD 1
ADD 5
ADD 4
ADD 6
FIND
DEL 5
FIND
|
1
2
|
