Недавно Леша завел себе домашнюю акулу. Акула — достаточно сложный домашний питомец в плане содержания, хотя бы потому, что за один раз она может съесть только ровно $$$k$$$ единиц однотипного корма.

Леша решил показать акулу своему другу Диме, но тот испугался ее и предложил Леше следующий спор. Дима принесет Леше некоторый корм, а Леша попытается скормить его акуле каким-либо образом (возможно, в несколько приемов). Если Леше не удастся этого сделать, он проиграл.

Дима разложил $$$n$$$ единиц имеющегося у него корма в ряд на столе так, что тип $$$i$$$-й единицы корма для акул на столе был равен $$$a_i$$$. Леша не знает, принесет ли Дима весь свой корм, но уверен, что Дима принесет последовательный интервал того, что у него сейчас на столе. Найдите количество интервалов корма таких, что Леша победит в заключенном пари!

Вы наверняка знаете, что такое перестановка, но на всякий случай, напомним:

Перестановкой из $$$n$$$ элементов называется последовательность $$$p_1, p_2, \dots, p_n$$$, в которой все числа от $$$1$$$ до $$$n$$$ встречаются один раз.

Для последовательности $$$a_1,a_2, \dots, a_n$$$ также определим количество инверсий как количество пар $$$i, j$$$ таких, что $$$i \lt j$$$ и $$$a_i \gt a_j$$$. Красотой последовательности длины $$$m$$$ назовем число $$$m$$$ минус количество инверсий в этой последовательности.

Вам дана перестановка из $$$n$$$ элементов. Разрешено вычеркнуть из нее любое количество чисел. Найдите, какую максимальную красоту последовательности можно получить.

Вам дано три целых числа. Вам требуется упорядочить их так, чтобы сумма первых двух была равна третьему или определить, что такого порядка не существует.

У Пети есть массив состоящий из $$$n$$$ чисел и любимое число $$$k$$$.

Для любого массива Петя умеет определять его привлекательность по формуле: $$$max(array)-min(array)$$$, где $$$max(array)$$$ обозначает максимальный элемент в массиве, а $$$min(array)$$$ — минимальный элемент массива.

Для того, чтобы массив приблизился по красоте к его любимому числу, Петя может удалить не более одного элемента из этого массива. В случае если он может получить массив с привлекательностью не больше числа $$$k$$$, то он называет изначальный массив — красивым.

Петя хочет, чтобы вы ответили на $$$q$$$ его вопросов. Каждый вопрос состоит из двух чисел $$$L$$$ и $$$R$$$. Ему интересно сколько различных красивых подотрезков массива лежит внутри данного отрезка от $$$L$$$ до $$$R$$$. Более формально, вам нужно найти количество различных пар чисел «l r» для которых выполняется: $$$L \le l \lt r \le R$$$ и массив $$$a_l, a_{l + 1}, \dots, a_r$$$ является красивым.

Недавно Леша нашел в библиотеке старинную книгу: «Путеводитель для путешествующих автостопом по галактике». В ней рассказывалось, что всего в галактике $$$n$$$ звезд, пронумерованных от $$$0$$$ до $$$n-1$$$, и для каждой звезды $$$i$$$ известно $$$f_i$$$ — звезда, на которую вас готовы подвезти от звезды $$$i$$$.

Леша захотел оценить насколько данный вид путешествий по галактике эффективен. Для этого он посчитал $$$c_i$$$ — количество различных звезд, которые можно посетить, начав путешествие со звезды $$$i$$$. Тогда привлекательностью автостопа назовем сумму $$$c_i$$$ по всем звездам.

Книга была настолько старой, что некоторые числа в ней оказались затерты. У вас есть прекрасная возможность доказать Леше, что автостоп — лучший способ путешествий по галактике: допишите затертые $$$f_i$$$ самостоятельно так, чтобы привлекательность автостопа была максимальна.

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

Осталось определиться, в каких составах будет проходить чемпионат. Друзья получили футболки с номерами от $$$1$$$ до $$$n$$$ так, что про друга с $$$i$$$-м номером известно, что его скилл в футболе численно равен $$$i$$$. Тогда сила команды это сумма сил отдельно взятых игроков.

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

Мальчику Вове очень нравятся раскраски. На этот раз, Вова решил использовать в качестве раскраски свою тетрадь в клеточку. Каждый лист имеет высоту в $$$n$$$ клеточек и ширину в $$$m$$$ клеточек. У Вовы есть фломастер, с помощью которого он и собирается раскрашивать листы тетради. Чтобы процесс раскраски был более интересным, Вова решил установить определенные правила:

• Каждая клетка должна быть либо польностью закрашена, либо не закрашена вовсе;
• Если Вова раскрасил клеточку $$$(x, y)$$$, то следующая закрашиваемая клетка должна быть соседней по стороне;
• Начинать раскрашивать можно с любой клетки;
• Можно закрасить ранее закрашенную клеточку, в таком случае ничего не произойдет, так как клетка уже была закрашена.

Вова хочет нарисовать все возможные варианты рисунков, которые можно получить, раскрашивая листы тетрадки по таким правилам. Вова интересуется, а сколько листов ему для этого понадобится (листы односторонние). Два рисунка будут считаться различными, если найдется такая клеточка $$$(x, y)$$$, что в одном рисунке она будет закрашена, а в другом нет.

В отделе полиции в Барвихе работают не самые профессиональные сотрудники. Так, для получения премии за $$$2018$$$ год, было решено немного исправить полицейский отчет.

Полицейский отчет — это последовательность $$$a_1, a_2, \dots, a_n$$$, где $$$a_i$$$ — сложность $$$i$$$-го раскрытого преступления. Для корректности работы программы все числа в отчете должны быть целыми.

Полицейские отчеты хранятся в программе «Bxcel». Программа имеет следующую защиту: при попытке подменить отчет за прошедшие годы, программа не сверяет измененный файл со старым полностью, а сверяет лишь некоторые статистические данные.

Два файла считаются программой одинаковыми, если одновременно совпадают среднее арифметическое чисел в этих файлах, а так же дисперсия этих чисел. То есть, если в первом файле среднее равно $$$m_1$$$, дисперсия равна $$$D_1$$$, а во втором $$$m_2$$$ и $$$D_2$$$ соответственно, то два файла считаются одинаковыми, если $$$m_1=m_2$$$ и $$$D_1=D_2$$$.

Дисперсия $$$D$$$ в «Bxcel» считается следующим образом ($$$m$$$ — среднее арифметическое):

$$$$$$D = \dfrac{1}{n} \sum_{i=1}^n {(a_i - m)^2}$$$$$$

Среднее арифметическое в свою очередь считается по формуле:

$$$$$$m = \dfrac{1}{n} \sum_{i=1}^n {a_i}$$$$$$

Обратите внимание, что дисперсия и среднее арифметическое могут являться не целыми числами.

Полицейский Леша решил убрать одно из раскрытых преступлений, а в замен дописать два вымышленных. Найдите любой способ сделать это так, чтобы «Bxcel» не обнаружила подмены.

Недавно вы устроились дилером в казино. В вашу задачу входит разложение карт в случайном порядке. В казино, в котором вы работаете, используется следующий алгоритм перемешивания новой колоды карт:

В качестве параметра $$$a$$$ передается упорядоченная колода из $$$n$$$ карт (карты пронумерованы от $$$0$$$ до $$$n-1$$$). В качестве параметра $$$s$$$ передается случайное $$$32$$$-битное целое беззнаковое число.

Только кажется этот алгоритм был скомпрометирован. Вы уже перемешали колоду и готовы к новой раздаче, когда узнали это. Случайный параметр перемешивания, к сожалению, никто никуда не записал в целях безопасности. Руководство предложило выход: перемешать колоду еще раз! Так, используя seed, который остался в памяти компьютера после первого перемешивания, перемешайте данную вам перемешанную колоду еще раз.

Каково будет удивление игрока, когда колода, заряженная в киоске будет разложена в другом порядке!

Город будущего — идеальный прямоугольник разбитый на $$$n \times m$$$ единичных квадратиков, в каждом из которых расположено здание. Для упрощения схемы города, названия зданий на ней сокращены до одной первой буквы.

Транспорт будущего достаточно быстрый и позволяет произвести мгновенный перелет от здания к зданию, если удовлетворены следующие особенности:

• Эти здания находятся в одной строке или столбце схемы.
• Названия этих зданий совпадают по первой букве.
• На пути между этими зданиями есть хотя бы еще одно здание, которое также совпадает по первой букве названия.

Например: abbba — невозможно, так как не выполняется 3-й пункт, ababa — возможно, так как есть еще одно здание a.

Доставка будущего — совершенно новый сервис, который пользуется транспортом будущего в городе будущего и доставляет пиццу будущего. Вам поручено произвести последнюю доработку в интеллектуальной системе доставки будущего — проверку зоны доставки клиента. Так, вам будет дано $$$q$$$ запросов «$$$x_1,y_1,x_2,y_2$$$», а вы, пожалуйста, проверьте, возможно ли мгновенно доставить пиццу транспортом будущего от здания «$$$x_1,y_1$$$» к зданию «$$$x_2,y_2$$$». Мгновенная доставка может осуществляться с помощью нескольких мгновенных переходов.

Вам дан массив $$$a_i$$$ длины $$$n$$$, состоящий только из нулей и единиц. Назовем абсолютностью такого массива некоторое целое число $$$c = |c_0 - c_1|$$$, где $$$c_0$$$ и $$$c_1$$$ — количество нулей и единиц в массиве соответсвенно. Абсолютной абсолютностью массива будем называть некоторое целое число $$$c_A$$$ равное максимальной абсолютности среди всех массивов, полученных путем замены в исходном массиве значений на непрерывном подотрезке (в том числе нулевой длины) на противоположные: единицы — на ноль, нуля — на единицу.

У вас есть $$$q$$$ операций изменения значения определенного элемента в массиве на противоположное. После каждой операции требуется определить абсолютную абсолютность массива.

У Валеры есть $$$n$$$ кроликов, пронумерованных от $$$1$$$ до $$$n$$$. Так как их численность быстро растет, он хочет разделить их на две группы: группа номер $$$0$$$ и группа номер $$$1$$$. Обозначим $$$f(x) = y$$$ — кролик с номером $$$x$$$ относится к группе номер $$$y$$$. Например, $$$f(3) = 1$$$ означает, что кролик с номером $$$3$$$ относится к группе номер $$$1$$$. Тогда, если есть два кролика с номерами $$$a$$$ и $$$b$$$, такими, что $$$a$$$ делится на $$$b$$$, то должно выполняться следующее условие: $$$f(a) = f(b)\ OR\ f(\frac{a}{b})$$$, где $$$OR$$$ — операция побитового "ИЛИ". Невыполнение этого условия приведет к войне между двумя группами. Для $$$m$$$ кроликов Валера уже определил группу, к которой будет относиться каждый из них, однако дальше он просит вашей помощи. Помогите ему найти количество способов разделить кроликов на две группы так, чтобы они не начали войну, а кролики, для которых Валера определил группу, были в соответствующих группах. Так как это число может быть достаточно большим, Валеру интересует остаток от деления этого числа на $$$10^9+7$$$.