C. Книжные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть полка и вы хотите положить на нее книги.

Вам задано $$$q$$$ запросов трех типов:

  1. L $$$id$$$ — положить книгу с номером $$$id$$$ на полку слева от самой левой существующей книги;
  2. R $$$id$$$ — положить книгу с номером $$$id$$$ на полку справа от самой правой существующей книги;
  3. ? $$$id$$$ — посчитать минимальное количество книг, которые нужно убрать с полки слева или справа, чтобы книга с номером $$$id$$$ стала самой левой или самой правой.

Можете считать, что первая книга, которую вы положите на полку, может иметь любую позицию (это неважно) и запросы типа $$$3$$$ всегда являются корректными (гарантируется, что книга в каждом таком запросе уже положена на полку). Также можете считать, что вы не кладете одну и ту же книгу на полку дважды, таким образом $$$id$$$ не повторяются в запросах первых двух типов.

Ваша задача — ответить на все запросы типа $$$3$$$ в порядке их появления во входных данных.

Заметьте, что после ответа на запрос типа $$$3$$$ все книги остаются на полке и их относительный порядок не меняется.

Если вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете посылать свой код.

Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Далее следуют $$$q$$$ строк. $$$i$$$-я строка содержит $$$i$$$-й запрос в таком же формате, как и в условии задачи. Гарантируется, что все запросы корректны (для запроса типа $$$3$$$ гарантируется, что книга в каждом таком запросе уже положена на полку, а для других типов гарантируется, что книга не была положена ранее).

Гарантируется, что во входных данных есть хотя бы один запрос типа $$$3$$$.

Для каждого запроса выполняется ограничение $$$1 \le id \le 2 \cdot 10^5$$$.

Выходные данные

Выведите ответы на запросы типа $$$3$$$ в порядке их появления во входных данных.

Примеры
Входные данные
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
Выходные данные
1
1
2
Входные данные
10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115
Выходные данные
0
2
1
Примечание

Посмотрим на первый тестовый пример и рассмотрим запросы:

  1. Полка будет выглядеть следующим образом: $$$[1]$$$;
  2. Полка будет выглядеть следующим образом: $$$[1, 2]$$$;
  3. Полка будет выглядеть следующим образом:$$$[1, 2, 3]$$$;
  4. Полка выглядит как $$$[1, \textbf{2}, 3]$$$, таким образом ответ равен $$$1$$$;
  5. Полка будет выглядеть следующим образом: $$$[4, 1, 2, 3]$$$;
  6. Полка выглядит как $$$[4, \textbf{1}, 2, 3]$$$, таким образом ответ равен $$$1$$$;
  7. Полка будет выглядеть следующим образом: $$$[5, 4, 1, 2, 3]$$$;
  8. Полка выглядит как $$$[5, 4, \textbf{1}, 2, 3]$$$, таким образом ответ равен $$$2$$$.

Посмотрим на второй тестовый пример и рассмотрим запросы:

  1. Полка будет выглядеть следующим образом: $$$[100]$$$;
  2. Полка будет выглядеть следующим образом: $$$[100, 100000]$$$;
  3. Полка будет выглядеть следующим образом: $$$[100, 100000, 123]$$$;
  4. Полка будет выглядеть следующим образом: $$$[101, 100, 100000, 123]$$$;
  5. Полка выглядит как $$$[101, 100, 100000, \textbf{123}]$$$, таким образом ответ равен $$$0$$$;
  6. Полка будет выглядеть следующим образом: $$$[10, 101, 100, 100000, 123]$$$;
  7. Полка будет выглядеть следующим образом: $$$[10, 101, 100, 100000, 123, 115]$$$;
  8. Полка выглядит как $$$[10, 101, \textbf{100}, 100000, 123, 115]$$$ , таким образом ответ равен $$$2$$$;
  9. Полка будет выглядеть следующим образом: $$$[10, 101, 100, 100000, 123, 115, 110]$$$;
  10. Полка выглядит как $$$[10, 101, 100, 100000, 123, \textbf{115}, 110]$$$, таким образом ответ равен $$$1$$$.