У вас есть полка и вы хотите положить на нее книги.
Вам задано \(q\) запросов трех типов:
- L \(id\) — положить книгу с номером \(id\) на полку слева от самой левой существующей книги;
- R \(id\) — положить книгу с номером \(id\) на полку справа от самой правой существующей книги;
- ? \(id\) — посчитать минимальное количество книг, которые нужно убрать с полки слева или справа, чтобы книга с номером \(id\) стала самой левой или самой правой.
Можете считать, что первая книга, которую вы положите на полку, может иметь любую позицию (это неважно) и запросы типа \(3\) всегда являются корректными (гарантируется, что книга в каждом таком запросе уже положена на полку). Также можете считать, что вы не кладете одну и ту же книгу на полку дважды, таким образом \(id\) не повторяются в запросах первых двух типов.
Ваша задача — ответить на все запросы типа \(3\) в порядке их появления во входных данных.
Заметьте, что после ответа на запрос типа \(3\) все книги остаются на полке и их относительный порядок не меняется.
Если вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете посылать свой код.
Примечание
Посмотрим на первый тестовый пример и рассмотрим запросы:
- Полка будет выглядеть следующим образом: \([1]\);
- Полка будет выглядеть следующим образом: \([1, 2]\);
- Полка будет выглядеть следующим образом:\([1, 2, 3]\);
- Полка выглядит как \([1, \textbf{2}, 3]\), таким образом ответ равен \(1\);
- Полка будет выглядеть следующим образом: \([4, 1, 2, 3]\);
- Полка выглядит как \([4, \textbf{1}, 2, 3]\), таким образом ответ равен \(1\);
- Полка будет выглядеть следующим образом: \([5, 4, 1, 2, 3]\);
- Полка выглядит как \([5, 4, \textbf{1}, 2, 3]\), таким образом ответ равен \(2\).
Посмотрим на второй тестовый пример и рассмотрим запросы:
- Полка будет выглядеть следующим образом: \([100]\);
- Полка будет выглядеть следующим образом: \([100, 100000]\);
- Полка будет выглядеть следующим образом: \([100, 100000, 123]\);
- Полка будет выглядеть следующим образом: \([101, 100, 100000, 123]\);
- Полка выглядит как \([101, 100, 100000, \textbf{123}]\), таким образом ответ равен \(0\);
- Полка будет выглядеть следующим образом: \([10, 101, 100, 100000, 123]\);
- Полка будет выглядеть следующим образом: \([10, 101, 100, 100000, 123, 115]\);
- Полка выглядит как \([10, 101, \textbf{100}, 100000, 123, 115]\) , таким образом ответ равен \(2\);
- Полка будет выглядеть следующим образом: \([10, 101, 100, 100000, 123, 115, 110]\);
- Полка выглядит как \([10, 101, 100, 100000, 123, \textbf{115}, 110]\), таким образом ответ равен \(1\).