В вашем отеле необычный лифт — вместо привычных кнопок для каждого этажа, в нём есть только две: + 3 и - 2, перемещающие лифт на три этажа вверх и на два этажа вниз соответственно.
Вы хотите попасть с этажа номер 0 (там находится лобби отеля) на этаж номер D (там находится ваш номер), но не хотите постоянно нажимать на кнопки. За какое минимальное число нажатий вы сможете добраться до D-го этажа?
В единственной строке дано одно целое число D ( - 1000 ≤ D ≤ 1000) — номер этажа, на который вы хотите попасть. Обратите внимание, что в отеле есть подземные этажи с отрицательными номерами.
Выведите одно число — минимальное число нажатий для перемещения с нулевого этажа на этаж с номером D.
1
2
-5
5
В первом примере из условия, чтобы попасть с нулевого этажа на первый, нужно один раз подняться на 3 этажа и 1 раз спуститься на 2 этажа, в итоге получится 2 нажатия кнопок.
Во втором примере из условия, чтобы спуститься на 5 этажей вниз, нужно один раз подняться на 3 этажа и 4 раза спуститься вниз на 2 этажа, таким образом, получится 5 нажатий кнопок.
Управляющий отелем давно мечтал приобрести новую мебель на свою дачу...
В Отель привезли $$$N$$$ новых стульев. Их нужно расставить во все комнаты гостиницы. Вместимость каждой комнаты $$$a_i$$$ гостей, то есть, изначально предполагалось, что в этой комнате будет ровно $$$a_i$$$ стульев. Администратор хочет сэкономить на расстановке стульев в комнатах и забрать «лишние» стулья на дачу.
Но есть условия, которые необходимо соблюдать при расстановке:
- в каждой комнате должен быть хотя бы один стул;
- во всех комнатах может не хватать только одинакового количества стульев.
Какое максимально возможное количество стульев может сэкономить администратор в данных условиях?
В первой строке вводится два числа $$$N$$$ ($$$1\le N\le 10^9$$$) — количество привезенных стульев и $$$K$$$ ($$$1\le K\le 100\,000$$$) — количество комнат в Отеле.
Далее в одной строке через пробел записаны $$$K$$$ натуральных чисел, не превосходящих $$$1000$$$ — вместимости комнат.
Гарантируется, что исходного количества стульев хватает для расстановки по комнатам с учетом необходимых требований.
Нужно вывести единственное число — количество стульев, которые останутся после максимально экономной расстановки стульев по комнатам.
20 5 2 3 4 5 6
5
В примере из условия если в первую комнату поставить 1, во вторую — 2, в третью — 3, в четвёртую — 4, а в пятую — 5 стульев, то в каждой из комнат будет не хватать ровно одного стула, а администратор сможет сэкономить ровно пять стульев.
Закончился туристический сезон, и почти все отдыхающие разъехались. Теперь у Портье почти не осталось работы, и он уже успел заскучать. Поначалу он пытался скоротать время, снова и снова убирая номера, решая судоку и раскладывая пасьянсы. Но все это ему быстро надоело.
Однажды он заметил, что один из гостей оставил на столе книгу. Портье придумал следующую игру: он открывает книгу на случайной странице, выбирает какое-то слово и выписывает его большими буквами на отдельном листе бумаги.
После этого он берёт монетку и кладёт её на первую букву слова. Затем много раз (возможно, бесконечное число) он делает следующую операцию: если выбранном слове есть еще одна такая же буква, как и та, на которой лежит монетка, то портье перекладывает эту монетку на любую такую же букву. Если же буква, на которой лежит монетка встречается ровно один раз, то портье сдвигает монетку на следующую букву, а если следующей буквы в слове нет, то игра завершается.
Например, если изначальное слово было «letovo», то монетка будет перемещаться следующим образом (положение монетки в отражено жирным подчёркнутым шрифтом):
- letovo
- letovo
- letovo
- letovo
- letovo
- letovo
- letovo
- ...
Обратите внимание, что в примере выше игра никогда не завершится: монетка будет бесконечно долго перемещаться между двумя буквами «o».
Помогите Портье: по данному вам слову длины n, состоящему только из строчных букв латинского алфавита, узнать завершается ли на этом слове придуманная им игра.
В первой строке дано число n (1 ≤ n ≤ 100 000) — длина строки.
Во второй строке дана строка s, строка состоит только из строчных букв латинского алфавита.
Выведите «YES», если игра завершается, и «NO» — в противоположном случае.
6
letovo
NO
3
abc
YES
3
aaa
NO
Отель представляет собой последовательность из $$$n$$$ зданий различной высоты, построенных вплотную друг к другу. Не так давно в Отель провели кабельное телевидение, которым все теперь с удовольствием пользуются. Но есть одна проблема: на крыше $$$m$$$-го здания осталась куча оборудования от спутникового телевидения, которое надо с неё спустить, и вам поручили это сделать.
Попасть с земли на крышу каждого из зданий можно только посредством переносной лестницы, длина которой не меньше, чем высота здания. А уже сверху можно свободно передвигаться между соседними крышами по постоянным лестницам.
Так как оборудование для спутникового телевидения большое и тяжёлое, то вместе с оборудованием вы можете только спускаться по лестницам. В случае, если два соседних дома имеют одинаковую высоту, то перемещаться между их крышами можно без каких либо ограничений, в том числе и с оборудованием.
Оказалось, что достать длинную лестницу не так уж и просто, поэтому необходимо найти минимальную длину лестницы, подходящей для демонтажа оборудования с крыши.
На первой строке вводится два целых числа $$$n, m$$$ $$$(1 \le m \le n \le 100\,000)$$$ — число зданий и номер здания, на котором находится оборудование, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ $$$(1 \le h_i \le 10^9)$$$ — высоты зданий.
Выведите одно целое число — минимальный размер лестницы, достаточной для демонтажа.
5 3 2 2 3 2 1
1
В данном примере вам достаточно лестницы длины $$$1$$$, так как вы можете подняться с её помощью на крышу пятого здания, далее добраться по лестницам между крышами на третью крышу, взять оборудование, после чего сначала спуститься по лестнице между третьей и четвертой, а затем — четвертой и пятой крышами. После этого можно спуститься с крыши пятого здания.
В ресторане отеля есть $$$n$$$ видов специй. Каждый день повар выбирает $$$m$$$ из них для главного блюда дня. Помощник главного повара тестирует блюдо и после этого оно поступает на обед в ресторан.
Известно, что у помощника есть аллергия на $$$k$$$ видов специй, имеющихся в ресторане. Сегодня он протестировал блюдо и аллергии не возникло.
На обед пришло $$$p$$$ человек, у каждого из которых тоже есть аллергия на некоторые виды специй. Попробуйте для каждого из участников обеда предположить, может ли у них возникнуть аллергия на главное блюдо?
В первой содержатся целые числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 100$$$) — число специй на складе и количество специй в главном блюде соответственно.
Далее в отдельной строке идет число $$$k$$$ ($$$0 \le k \le n$$$) — число специй, на которые аллергия у помощника повара.
В следующих $$$k$$$ строках содержатся названия специй, на которые есть аллергия у помощника повара.
В следующей строке написано число $$$p$$$ ($$$1 \le p \le 100$$$) — число людей на обеде. Далее идет $$$p$$$ блоков, описывающих специи, опасные для $$$i$$$-го участника обеда. Каждый блок начинается строкой с числом $$$n_i$$$ ($$$0 \le n_i \le n$$$) — количеством продуктов, на которые аллергия у $$$i$$$-го человека, вслед за которым идёт $$$n_i$$$ строк с названиями аллергенных специй.
Все названия — слова из латинских букв длиной не более 30 символов.
Для каждого из $$$p$$$ запросов выведите на отдельной строке одно слово:
- NO, если обед будет полностью безвреден для очередного гостя;
- YES, если в главном блюде есть специя аллергенная для гостя;
- MAYBE, если при таких исходных данных возможна и та, и другая ситуация.
7 3 3 pepper imbir cumin 3 1 pepper 3 cumin fenugreek lime 2 imbir lime
NO YES MAYBE
Вы с друзьями уже давно заехали в отель, но только сейчас выяснилось, что в отеле существуют так называемые «Тихие часы». Во время этих часов все должны находиться в своих комнатах, и обойти это ограничение нельзя, потому ключи от комнат на время «Тихих часов» забирает персонал отеля. К счастью, вам повезло и вы с друзьями живёте на одном этаже, в последовательных комнатах с номерами от 1 до n. Расстояние между соседними комнатами равно 5 метрам.
Вы пришли к достаточно изящной идее, которая поможет справиться со столь сложной ситуацией. За одну ночь под всеми комнатами вы проложили конвейер из 3n ячеек, позволяющий перевозить посылки. Соседние ячейки, так же, как и комнаты, находятся на расстоянии 5 метров друг от друга. Ячейки конвейера с номерами от n + 1 до 2n находятся под комнатами друзей, ячейки с номерами от 1 до n – левее комнаты номер 1, а ячейки с номерами от 2n + 1 до 3n – правее комнаты с номером n.
В один из таких «Тихих часов» каждый друг отправил посылку одному другому другу. Для того, чтобы перемещать посылки, есть две кнопки: «ВПРАВО» и «ВЛЕВО», сдвигающие конвейер на 5 метров вправо и влево соответственно.
Вы с друзьями захотели узнать, какое минимальное число нажатий на кнопки потребуется, чтобы все посылки были доставлены их адресатам и не выпали с краёв конвейера.
Первая строка входных данных содержит одно целое число n (2 ≤ n ≤ 100 000) — число друзей, обменивающихся посылками.
Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ n, ai ≠ i) — номер друга, которому адресована посылка i-го из друзей.
Выведите одно целое число — минимальное число нажатий, которое потребуется, чтобы все посылки дошли до адресатов.
4
2 3 2 1
5
Разберём пример из условия. Сначала можно 1 раз нажать кнопку «ВПРАВО», после этого второй друг получит посылку от первого, а третий — от второго. После этого необходимо 2 раза нажать на кнопку «ВЛЕВО», тогда второй друг получит посылку от третьего. И наконец, нужно ещё 2 раза нажать кнопку «ВЛЕВО», после чего первый друг получит посылку от четвёртого. Итого потребуется 5 нажатий.
Недавно руководители Отеля поняли, что гостей становится все больше и нужно расширять штат. С чего бы начать? Первым на работу взяли нового Портье.
Но вот незадача, Портье ещё не успел освоиться на новом месте, как уже начались проблемы. Недовольные постояльцы вызвали его к себе в номер на шестом этаже, однако, по неопытности он заблудился и зашел в комнату $$$404$$$!!! А там... Лабиринт.
Лабиринт представляет собой последовательность из $$$n$$$ дверей, расположенных друг за другом на одном этаже. Каждая $$$i$$$-я дверь покрашена в какой-то цвет $$$a_i$$$, причём на этаже ровно по две двери каждого из цветов.
Допустим, что две разные двери $$$i$$$ и $$$j$$$ покрашены в один и тот же цвет. В таком случае, если Портье зайдёт в $$$i$$$-ю дверь слева, то он окажется между $$$j$$$-й и $$$(j+1)$$$ -й дверьми и сможет дальше зайти в одну из них. Если же он зайдёт в $$$i$$$-ю дверь справа, то он окажется между $$$j$$$ -й и $$$(j - 1)$$$-й дверьми и далее сможет зайти в одну из них. Если $$$j = n$$$, то войдя в $$$i$$$-ю дверь слева, он окажется правее последней двери и выберется из лабиринта. Если же $$$j = 1$$$, то зайдя в $$$i$$$-тую дверь справа он окажется между первой дверью и началом лабиринта и сможет зайти только в первую дверь.
Изначально Портье находится левее первой двери и очень спешит выбраться. Пожалуйста, помогите ему найти минимальное количество проходов через двери для выхода из лабиринта.
В первой строке находится чётное число $$$n$$$ $$$(2 \le n \le 200\,000)$$$ — количество дверей в лабиринте.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — цвет $$$i$$$-й двери в последовательности. Гарантируется, что в лабиринте ровно по две двери каждого из цветов.
На единственной строке выведите минимальное количество проходов через двери, которое потребуется для того, чтобы выбраться из дверного лабиринта.
6 1 2 1 3 3 2
5
8 3 2 3 2 1 4 1 4
8
Ниже на картинке изображено пояснение к первому примеру из условия.
В Отеле все комнаты пронумерованы числами длины $$$n$$$ (возможно, с ведущими нулями). Как и заведено во всех отелях, при заселении Вам выдали ключ, на котором написан номер, также состоящий из $$$n$$$ цифр (возможно, с ведущими нулями).
В Отеле ключ открывает комнату, только если выполнено следующее условие. Для каждого $$$1 \le i \lt n$$$, сумма $$$i$$$-й и $$$(i+1)$$$-й цифры номера комнаты должна быть равна $$$i$$$-й цифре ключа по модулю 10. Помимо этого, последняя цифра ключа должна быть равна сумма первой и последней цифры номера комнаты по модулю 10.
Найдите все номера комнат, которые открывает имеющийся у Вас ключ.
На первой строке дано число $$$n$$$ ($$$2 \le n \le 100\,000$$$) — количество цифр в номерах комнат.
Во второй строке написан номер ключа, гарантируется, что это строка длины $$$n$$$, состоящая только из цифр.
На первой строке выведите количество комнат, открываемых ключом.
На каждой следующей строке выведите каждый из номеров этих комнат, по одному номеру в строке. Каждый номер комнаты должен представлять собой строку длины $$$n$$$, состоящую только из цифр.
5 59237
2 14576 69021
5 25575
2 02325 57870
Поясним второй пример. Ключ с номером 25575 открывает комнату 57870 так как: $$$$$$ 2 = (5 + 7) \mod 10 $$$$$$ $$$$$$ 5 = (7 + 8) \mod 10 $$$$$$ $$$$$$ 5 = (8 + 7) \mod 10 $$$$$$ $$$$$$ 7 = (7 + 0) \mod 10 $$$$$$ $$$$$$ 5 = (0 + 5) \mod 10 $$$$$$
Можно проверить аналогичные равенства и для комнаты 02325. Утверждается, что больше никакие комнаты этим ключом открыть нельзя.
Вы с друзьями устроили марафон просмотра фильмов про отели, проголодались и решили заказать пиццу. Пока вы выбирали, с какого фильма начать просмотр, курьер с пиццей уже почти приехал. Вам пришло уведомление, что «Курьер уже почти на месте», но прошло уже 5 минут, а пицца всё ещё не доставлена. Что же случилось?
Курьер действительно приехал по нужному адресу, но не может понять, действительно ли это тот отель, в который заказали пиццу. Вывеска отеля представляет из себя прямоугольник, состоящий из $$$n$$$ строк по $$$m$$$ заглавных латинских букв в каждой. И курьер не имеет ни малейшего понятия, где на ней написано название отеля.
Курьер попросил помощи у прохожего, на что тот ответил, что не помнит, как называется отель, зато знает, как найти название на вывеске. Он рассказал, что ещё совсем недавно у курьера не возникло бы проблем: на вывеске было только слово «HOTEL» и название отеля (также состоящее из 5 букв). Название начинается с буквы «L», поэтому хозяин решил оформить вывеску так: он написал слово «HOTEL» так, чтобы соседние буквы граничили по стороне, а после этого так же (с тем же расположением букв относительно предыдущих) написал название, начав его с последней буквы слова «HOTEL». Для лучшего понимания посмотрите, как могла бы выглядеть вывеска отеля с названием LUCKY:
Хозяину отеля так понравилось рисовать буквы, что он решил заполнить ими вообще все клетки матрицы-вывески. Чтобы у посетителя остался шанс найти название, хозяин вписал буквы так, чтобы ни в каком другом месте нельзя было прочитать слово «HOTEL».
Зная всю эту информацию, курьер смог выяснить название отеля. А сможете ли вы?
В первой строке даны два числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 100)$$$ — размеры вывески.
В следующих $$$n$$$ строках дана сама матрица-вывеска. Каждая из строк состоит из $$$m$$$ заглавных букв латинского алфавита.
Гарантируется, что слово «HOTEL» встречается в матрице ровно один раз.
Выведите единственное слово из пяти заглавных латинских букв — название отеля.
5 9 CCCCCCCCC CHOTCCCCC CCCELILCC CCCCCCIAC CCCCCCCCC
LILIA
12 7 DGKETCA PKETEUB ZETOTEJ ETOHOTE SETOTEU NIETEWM LXPEOHP PPXLJTR MCLUHFN RHFCEFL NRVKWMJ FEFYAJL
LUCKY
В отеле есть традиция устраивать публичное вечернее кормление всех живущих в отеле кошек. Всего в нём живёт $$$n$$$ кошек, и имеется по одной личной миске для каждой из кошек и одна большая общая миска, из которой может наесться любое количество питомцев. Личные миски кошек расположены в один ряд, а общая стоит отдельно от всех остальных.
Ваши питомцы хорошо обучены есть строго либо из своей миски, либо из большой общей миски. Когда $$$i$$$-й котик ест из своей миски, то он выглядит милым на некоторую величину $$$a_i$$$. Если бы все котики спокойно кушали из своей миски, то общая милота ужина вычислялась бы как сумма $$$a_i$$$ всех котиков.
Но не все так просто, некоторые питомцы слишком увлекаются едой и начинают толкать своего соседа справа во время трапезы, тем самым мешая другим кушать и портя общую милоту ужина. Допустим, вы знаете, что $$$i$$$-й котик толкается, тогда вы можете избежать толкания, если посадить либо $$$i$$$-го котика, либо $$$i+1$$$-го котика ужинать за общую миску, но в таком случае отсаженный котик уже не будет привносить милоту в общую милоту ужина. Вам известно, что толкание $$$i$$$-го котика своего соседа справа отнимает $$$q_i$$$ общей милоты ужина. Таким образом, общая милота ужина вычисляется как сумма милоты всех котиков, которые ужинают за своей миской, из которой вычитаются все $$$q_i$$$ котиков, которые толкают своего соседа на позиции $$$i+1$$$.
Сегодня в отель заселились очень важные гости, и вы хотите посадить котиков ужинать так, чтобы общая милота ужина была максимальной.
Первая строка содержит одно целое число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — количество котиков.
Вторая строка содержит $$$n$$$ целых чисел $$$(1 \le a_i \le 10^6)$$$, где $$$a_i$$$ — милота $$$i$$$-го котика.
Третья строка содержит одно число $$$m$$$ $$$(0 \le m \lt n)$$$ — количество котиков, толкающих своего соседа.
Каждая из последующих $$$m$$$ строк содержит два числа $$$k_i$$$ $$$(1 \le k_i \lt n)$$$ и $$$q_{k_i}$$$ $$$(1 \le q_{k_i} \le 10^6)$$$, обозначающую, что если $$$k_i$$$ котик толкается, то общая милота ужина уменьшается на $$$q_{k_i}$$$.
В качестве ответа выведите одно число — максимально возможную милоту ужина.
5 10 20 30 40 50 2 1 150 3 25
115
6 1 7 4 1 2 2 3 1 5 3 3 5 1
14
В первом примере можно отсадить первого питомца к общей миске, а остальных отправить ужинать за свои миски. Суммарная милота благодаря тому, что котики кушают за своими мисками, будет равна $$$20 + 30 + 40 + 50 = 140$$$, но третий котик будет толкать четвертого, поэтому из этой суммы вычитается $$$q_3 = 25$$$. Таким образом, ответ на этот пример равен $$$115$$$.
Недавно директору Ресторана Отеля пришла в голову следующая мысль: «Все какое-то обычное. Надо что-то модернизировать!» Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.
Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО «В Гараже у Петровича». И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили $$$n$$$ столов и приготовили $$$n$$$ блюд. Все блюда попарно различны и имеют номера от $$$1$$$ до $$$n$$$. Изначально, блюда по мере готовности как-то расставили по $$$n$$$ столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, $$$i$$$-е блюдо должно оказаться на $$$i$$$-м столе.
Рядом с каждым столом изначально стоит робоант. Далее каждый робоант независимо от других может выполнять следующую операцию неограниченное число раз: пусть сейчас робоант стоит у $$$i$$$-го стола. Тогда, если у него с собой нет ни одного блюда, он может взять (а может и не брать) блюдо в данный момент, находящееся на $$$i$$$-м столе и перейти к любому $$$j$$$-му столу при условии, что $$$i$$$ и $$$j$$$ имеют общий делитель больший $$$1$$$. Далее, если у робоанта есть с собой блюдо, он может положить его на $$$j$$$-й стол (а может и не класть).
Теперь директор просит помочь ему у написать программу, которая определит, смогут ли его робоанты расставить все блюда по местам.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество столиков в Ресторане.
Во-второй строке записано $$$n$$$ различных целых чисел $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le n$$$) — номера блюд изначально расставленных на соответственно $$$1$$$-й, $$$2$$$-й, ... $$$n$$$-й столиках.
Выведите «YES», если робоанты смогут расставить все блюда по местам, и «NO» в противном случае случае.
9 1 8 3 6 5 4 7 2 9
YES
6 6 2 3 5 4 1
NO
Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:
- Берёт со $$$2$$$-го стола $$$8$$$-е блюдо, перемещается к $$$8$$$-му столу, кладет блюдо.
- Берёт с $$$8$$$-го стола $$$2$$$-е блюдо, перемещается ко $$$2$$$-му столу, кладет блюдо.
- Перемещается к $$$4$$$-му столу.
- Берёт с $$$4$$$-го стола $$$6$$$-е блюдо, перемещается к $$$6$$$-му столу, кладет блюдо.
- Берёт с $$$6$$$-го стола $$$4$$$-е блюдо, перемещается к $$$4$$$-му столу, кладет блюдо.
Можно доказать, что во втором примере невозможно расставить все блюда по местам.
Как известно, в Отеле скучно не бывает: то фуршет, то номерки какие-то загадочные. А вот сейчас, для гостей опять подготовили нечто невероятное: приезжает Звезда.
Звезды — народ причудливый, вот например, Звезда, приехавшая в Отель, боится больших скоплений людей, поэтому поклонников на автограф-сессии будет принимать в специальном кабинете и только по одному, все же остальные гости будут ожидать в зале. И все бы хорошо, человечество давно придумало очереди, только вот во время сессии проходит фуршет, поэтому все разбредутся по залу и никакой очереди в ее привычном понимании устроить не получится и САО (служба администрирования очередей) решила обратиться к вам.
Вас просят написать систему учета людей, которая должна уметь выводить номер текущего первого в очереди гостя, добавлять людей в очередь и удалять из нее. Но мало того, что неразбериха с фуршетом, САО ещё и по неизвестной нам причине поощряет использование знакомств и связей в личных корыстных целях (в народе «блат»): если в зал приходит человек $$$x$$$, то он хочет найти своего друга $$$y$$$ и, если $$$y$$$ находится в зале, то $$$x$$$ в очереди становится прямо за ним, иначе $$$x$$$ помещается системой в конец очереди. Также может произойти такое, что гостю надоело ждать и тогда он просто уходит из зала ожидания и исключается из очереди.
Конечно, обработка событий по видео-камерам — увлекательный процесс, но САО решили, что проще будет дать уже готовую последовательность данных. Итак, вашей системе нужно обрабатывать следующие запросы:
- in x y — в зал фуршета приходит гость с номером $$$x$$$, который дружит с гостем номер $$$y$$$. Если $$$y$$$ уже находится в очереди, то $$$x$$$ встает за ним, иначе в конец. Стоит отметить, что гости очень восхищаются Звездой и могут приходить и не по одному разу.
- out x — гостю под номером $$$x$$$ надоело ждать и он уходит (гарантируется, что в данный момент гость с таким номером находится в зале).
- check — Звезда готова дать очередной автограф и САО хочет узнать, кто первый в очереди (после этого счастливец получит автограф и уйдет по своим делам). Если очередь пуста, выведите $$$-1$$$.
В первой строке вводится единственное натуральное число $$$q$$$ ($$$1 \leq q \leq 200\,000$$$) — количество запросов. Далее в $$$q$$$ строках вводятся вышеописанные запросы. Все числа, содержащиеся в запросах натуральные и не превосходят $$$10^8$$$.
На каждый запрос $$$check$$$ в отдельной строке выведете номер первого человека в очереди.
10 in 1 1 in 2 1 in 3 1 in 4 2 check out 4 check in 5 6 in 6 5 check
1 3 2
10 check in 10 5 in 9 3 in 6 7 out 6 in 5 3 in 3 4 check in 7 2 in 2 8
-1 10