В этот жаркий Санкт-Петербургский полдень стажёр Яндекса Аркадий сидел в офисе и вносил последние правки в свою дипломную работу. После нескольких часов тяжких трудов он решил развеяться и прогуляться до торгового автомата на первом этаже, чтобы купить бутылку своего любимого напитка Квас-Класс.

Стоит отметить, что в офисе установлен довольно необычный торговый автомат. Он принимает только монеты достоинством один рубль и купюры достоинством один миллион рублей, и при этом продаёт только бутылки напитка Квас-Класс ценой r рублей за штуку. Изначально у Аркадия есть b банкнот достоинством миллион рублей и c монет по одному рублю. В автомате изначально находятся d рублёвых монет, которыми он может давать сдачу. Процесс покупки одной бутылки напитка устроен следующим образом.

1. Аркадий вставляет в автомат x банкнот и y монет, то есть общая загруженная сумма составляет z = 10⁶·x + y.
2. Затем он нажимает на кнопку совершения покупки. Если z оказывается меньше r, то автомат просит внести ещё денег.
3. Если z больше либо равно r, то автомат пытается выдать Аркадию сдачу. Поскольку автомат может выдавать сдачу только монетами, то количество находящихся в нём монет в один рубль (при этом не учитываются монеты, вставленные для совершения именно этой покупки) должно быть не менее z - r. Если монет для выдачи сдачи недостаточно, то покупка не состоится.
4. Если z ≥ r и в автомате достаточно монет для того, чтобы выдать Аркадию сдачу (или сдача вообще не требуется, то есть z = r), происходит покупка. Автомат забирает себе x банкнот и y монет (которые могут быть использованы для выдачи сдачи при следующих покупках), после чего возвращает Аркадию z - r монет и выдаёт бутылку желанного напитка.

Хотя Аркадий пришёл купить только одну бутылку, он всё же программист, так что ему интересно, какое максимально количество бутылок он смог бы приобрести, если бы действовал оптимально? Можете считать, что в автомат загружено заведомо достаточное количество бутылок напитка Квас-Класс (что, к сожалению, далеко не всегда выполнено в реальной жизни).

Наибольшей возрастающей подпоследовательностью (НВП) массива a₁, ..., a_n называется последовательность индексов 1 ≤ i₁ < ... < i_k ≤ n, такая что a_i1 < ... < a_ik и значение k максимально возможное. Наибольшая убывающая подпоследовательность (НУП) определяется аналогично.

В самой свежей задаче для собеседований в Яндекс вам даётся перестановка p = (p₁, ..., p_n) чисел 1, 2, ..., n, в которой требуется выбрать НВП и НУП не имеющие общих элементов, или определить, что это невозможно сделать. Формально, требуется выбрать две последовательности индексов i₁ < ... < i_k и j₁ < ... < j_l, такие что:

• a_i1 < ... < a_ik;
• b_j1 > ... > b_jl;
• k равняется длине НВП в p;
• l равняется длине НУП в p,
• все индексы i₁, ..., i_k, j₁, ..., j_l различны.

Евгений занимается в Яндексе анализом больших данных. Недавно он решил немного отдохнуть, взял отпуск, и уехал в замечательный образовательный центр на берегу Чёрного моря преподавать школьникам машинное обучение и анализ данных.

По вечерам он идёт на набережную, где расположены n неплохих ресторанов, пронумерованных целыми числами 1, 2, ..., n, при этом ресторан с номером i находится на позиции i вдоль набережной. Евгений начинает в позиции 0 с запасом в e единиц энергии. Изначально желудок Евгения пуст и он тратит одну единицу энергии на перемещение в соседнюю позицию (например из позиции 0 в позицию 1, где расположен ресторан с номером 1). В течение вечера может происходить следующее.

1. Если в некоторый момент времени Евгений находится в позиции i и при этом он уже съел сегодня x единиц еды, то он может совершить операцию перемещения в позиции i - 1 или i + 1 потратив x + 1 единицу энергии.
2. Если Евгений находится в позиции i от 1 до n включительно и ещё не заходил этим вечером в ресторан с номеров i, то он может пойти туда. Евгений знает, что в результате посещения этого ресторана он съест ровно a_i единиц еды. На это действие Евгений не тратит энергии (жеванием можно пренебречь).
3. Если в некоторый момент времени Евгений снова оказывается в позиции 0, то он может принять решение остановится и пойти обратно в образовательный центр. Это действие так же не требует затрат энергии.

Поскольку Евгений занимается машинным обучением и смежными областями, он попросил вас посчитать максимальное количество еды, которое он может съесть и затем вернуться в образовательный центр в точке 0 если будет действовать оптимально.

Вам скорее всего известно, что основным продуктом компании Яндекс является поисковик, о котором и пойдёт речь в данной задаче.

В рамках данной задачи будет считать, что поисковик работает с базой данных, которая может быть представлена как строка s длины n. Система разрешается пользователям делать произвольные текстовые запросы к базе данных, в качестве ответа на эти запросы будет выведен список всех вхождений запроса в базу. Вхождение в базу называется появление текста-запроса в качестве подстроки строки s.

Алисе скучно, поэтому она развлекает себя тем, что открывает поисковик и вводит туда различные запросы. Изначально перед Алисой пустое текстовое поле. Каждый раз она изменяет предыдущий запрос ровно на одну букву, дописывая её в начало или в конец запроса по своему усмотрению. Алиса проделывает такую операцию ровно n раз.

В этом процессе Алисе нравится смотреть как на экране появляются все вхождения и как сильно может изменить их количество после добавления одного символа. Алиса хочет протестировать как поведёт себя поисковик если ему потребуется выводить очень много данных, поэтому она хочет выбрать такую последовательность приписываний букв в начало или конец строки, что суммарное количество вхождений всех строк-запросов в строку базы данных s будет максимально. Какое максимальное значение может получить Алиса?

Это интерактивная задача.

Алиса — голосовой помощник недавно представленный компанией Яндекс. Одним из направлений развития голосового помощника является добавление различных игр в которые Алиса сможет играть с пользователями, чтобы развлечь их. В этой задаче рассматривается игра со следующими правилами.

1. В начале Алиса называет некоторое число n и загадывает перестановку чисел от 1 до n обозначаемую p₁, p₂, ..., p_n.
2. Целью игры является сказать Алисе на какой позиции в изначальной перестановке находился элемент равный n.
3. Единственная операция, доступная игроку, это выбрать некоторую позицию i. После этого Алиса увеличивает значение p_i на один и сообщает количество различных элементов в текущем массива p₁, p₂, ..., p_n.

В игре есть возможность выбрать из нескольких уровней сложности. На последнем уровне игроку требуется угадать позицию числа n в изначальной перестановке за не более чем 50·n запросов. Вы ведёте разработку собственного голосового помощника Бориса и хотите научить его играть в эту игру, чтобы можно было поместить два телефона друг напротив друга и наблюдать битву искусственных интеллектов.

В начале Алиса сообщает игроку значение числа n (1 ≤ n ≤ 1000). Затем игрок может не более 50·n раз сделать запрос вида «0 x», где 0 означает, что игрок делает запрос, а x является позицией в массиве от 1 до n включительно, и означает, что Алиса должна увеличить значение p_x на один и сообщить количество различных элементов в массиве p после этого действия.

Как только вы уверены в своём ответе (или у вас кончились доступные запросы) вам необходимо вывести «1 x», где 1 означает вывод ответа, а x является собственно ответом, то есть догадкой, что в начале игры было выполнено p_x = n. Ваша программа должна завершиться как только выведет ответ, в противном случае вы можете получить непредсказуемый результат проверки.

Инженер Яндекса Иван — очень скрупулёзный человек, из тех кто никогда не создаст массив на большее количество элементов, чем ему действительно требуется.

Сегодня у Ивана есть массив из n различных целых положительных чисел a₁, a₂, ..., a_n, который он хочет положить в хеш-таблицу. Для этого он собирается выбрать некоторое значение m — количество корзин в хеш-таблице, а затем отправить число x в корзину . Таким образом, число a₁ попадёт в корзину h(a₁), a₂ попадёт в корзину h(a₂) и так далее.

Настолько же сильно, насколько Иван любит порядок, он ненавидит коллизии. Поэтому он хочет выбрать значение m таким образом, чтобы все значения были различными. От вас требуется найти подходящее m. Поскольку эффективность во всём является одной из целей инженера, работающего с большими данными, Иван просит вас выбрать среди всех подходящих m минимальное.