Сегодня Петя снова играл со своим другом — роботом Петей++.

Сегодняшняя игра заключается в том, что Петя++ загадывает некое число $$$n$$$. Затем он выписывает числа от $$$1$$$ до $$$n$$$ на листике. Теперь он вычёркивает каждое число, которое делилось на 2 — маркером одного цвета, а число, которое делилось на 3 — маркером другого цвета.

Пете стало интересно, сколько существует таких чисел, что они были зачёркнуты ровно один раз?

Сегодня двоичный паук решил сплести себе самую удобную паутину!

Известно, что дом двоичного паука представляет собой $$$n$$$ столбиков, для каждого из которых известна его высота $$$a_i$$$.

Теперь паук хочет выбрать самый уютный уголок. Уютным уголком считается такой непрерывный подотрезок из столбиков, в котором все высоты $$$\le x$$$. На нём наш герой будет плести паутину. Конечно же, среди всех таких возможных отрезков он хочет выбрать как можно более длинный для того, чтобы пауку было как можно просторнее.

Найдите длину наидлиннейшего подходящего отрезка.

Сегодня компания Interplanetary Software Inc. решила провести опыт по изучению марсианских чисел.

У вас есть число $$$a$$$. Пара чисел $$$(x; y)$$$ является марсианской, если наибольший общий делитель этих двух чисел равен 1.

Компания решила исследовать все числа на отрезке $$$[l; r]$$$ и определить, сколько чисел из отрезка образуют марсианскую пару с числом $$$a$$$.

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

Казимир знает, что он хочет высадить в ряд ровно $$$n$$$ яблонь. Также он знает, что высота каждой яблони среди доступных сейчас характеризуется уникальным числом от $$$1$$$ до $$$n$$$. Конечно же, высаживать деревья надо по феншую, а именно: высоты соседних в ряду деревьев не должны отличатся более, чем на 2.

Также Казимир считает, что самый живописный отрезок — отрезок $$$[l; r]$$$. Поэтому он хочет высаживать туда деревья так, чтобы сумма их высот была как можно больше. Вам требуется помочь Казимиру Казимировичу и найти оптимальную расстановку яблонь в саду, то есть такую, чтобы она была расстановкой по феншую, а также среди всех таких она должна иметь наибольшую сумму высот деревьев на подотрезке.

Если ответов может быть несколько, выведите любой из них.

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

Теперь уставшего путника нужно хорошенько накормить. У лесника дома, к счастью, оказалось $$$n$$$ блюд, каждое из которых характеризуется своей пищевой ценностью $$$a_i$$$. Добрый лесник запланировал для Казимира Казимировича $$$q$$$ обедов, на обеде с номером $$$j$$$ лесник может попробовать все блюда с номерами от $$$l_j$$$ до $$$r_j$$$. Для обеда введем понятие насыщенности — минимальное значение $$$a_i - i$$$ по всем блюдам, разрешенным на данном обеде.

Так как Казимир Казимирович — уважающий себя путник, он хочет максимизировать насыщенность каждого обеда, поэтому перед началом каждого приема пищи он может незаметно поменять порядок блюд из разрешенного отрезка (обратите внимание, что в таком случае номер некоторых блюд может измениться). Другими словами, Казимир Казимирович может заменить значения $$$a_l, a_{l + 1}, ..., a_{r - 1}, a_{r}$$$ на любую перестановку этих значений, а уже потом посчитать насыщенность обеда.

Но Казимир Казимирович также очень благодарный путник, поэтому после каждого обеда он возвращает все блюда на исходные места. Другими словами, перед каждым обедом значения блюд $$$a_l, a_{l + 1}, ..., a_{r - 1}, a_{r}$$$ должны быть такими же, как изначально, и перестановка этих значений на текущем обеде никак не влияет на следующие обеды.

Для каждого из обедов определите его максимально возможную насыщенность.

Напомним, что перестановкой чисел называется любое их переупорядочивание, например для массива $$$[1, 5, 6]$$$ это могут быть $$$[1, 5, 6]$$$, $$$[1, 6, 5]$$$, $$$[5, 1, 6]$$$, $$$[5, 6, 1]$$$, $$$[6, 1, 5]$$$, $$$[6, 5, 1]$$$.