Задана перестановка \(p_1, p_2, \dots, p_n\), то есть такой массив длины \(n\), что каждое число от \(1\) до \(n\) встречается в нём ровно один раз.

Найдите количество таких пар индексов \((l, r)\) (\(1 \le l \le r \le n\)), что медиана последовательности \(p_l, p_{l+1}, \dots, p_r\) равна заданному числу \(m\).

Медианой последовательности называется значение такого элемента, который находится в середине последовательности после её сортировки по неубыванию. Если последовательность имеет чётную длину, то имеется ввиду левый из двух средних элементов.

Например, если последовательность \(a=[4, 2, 7, 5]\), то её медиана равна \(4\), так как после сортировки последовательность примет вид \([2, 4, 5, 7]\) и левый из двух средних элементов равен \(4\). Медиана последовательности \([7, 1, 2, 9, 6]\) равна \(6\), так как после сортировки \(6\) будет находится в середине последовательности.

Напишите программу, которая найдет количество пар индексов \((l, r)\) (\(1 \le l \le r \le n\)), что медиана последовательности \(p_l, p_{l+1}, \dots, p_r\) равна заданному числу \(m\).

Поликарп тренирует свое умение решать задачи. У него есть список из \(n\) задач со сложностями \(a_1, a_2, \dots, a_n\) соответственно. Его план состоит в том, чтобы тренироваться ровно \(k\) дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно \(n\) задач ровно за \(k\) дней.

Таким образом, каждый день Поликарп решает последовательность подряд идущих (последовательных) задач с самого начала списка. Он не может пропускать задачи или решать их несколько раз. В итоге за \(k\) дней он решит \(n\) задач.

Полезность \(j\)-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение \(j\)-го дня (то есть если он решит задачи с номерами от \(l\) до \(r\) в течение какого-то дня, тогда полезность этого дня равна \(\max\limits_{l \le i \le r}a_i\)). Общая полезность его тренировки — это сумма полезностей по всем \(k\) дням его тренировки.

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

Например, если \(n = 8, k = 3\) и \(a = [5, 4, 2, 6, 5, 1, 9, 2]\), одним из возможных способов с максимальной общей полезностью является следующий: \([5, 4, 2], [6, 5], [1, 9, 2]\). Здесь общая полезность равна \(5 + 6 + 9 = 20\).

В ряд стоят \(n\) прямоугольников. Каждый из них вы можете либо повернуть на \(90\) градусов, либо оставить как есть. Если вы поворачиваете прямоугольник, то его высота станет шириной, а ширина — высотой. Заметьте, что вы можете повернуть любое количество прямоугольников, а так же вы можете повернуть все или не поворачивать ни один. Вы не можете менять порядок следования прямоугольников.

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

Наташа собирается полететь на Марс. Ей необходимо построить ракету, которая собирается из нескольких ступеней в определённом порядке. Каждая из ступеней описывается одной строчной буквой латинского алфавита. Тем самым ракета описывается строкой — конкатенацией букв, соответствующих ступеням.

Всего на складе есть \(n\) ступеней. Ракета должна содержать ровно \(k\) из них. Ступени в ракете должны быть упорядочены по весу. После ступени с некоторой буквой можно ставить только ступень с буквой, идущей хотя бы на две позиции позже в алфавите (то есть через одну букву или более). Например, после буквы 'c' нельзя ставить буквы 'a', 'b', 'c' и 'd', зато можно ставить 'e', 'f', ..., 'z'.

Чтобы ракета летела максимально далеко, нужно, чтобы её вес был минимален. Вес ракеты равен сумме весов её ступеней. Ступень весит столько тонн, каков номер её буквы в алфавите. Иными словами, ступень 'a' весит одну тонну, 'b' весит две тонны, а 'z' — \(26\) тонн.

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

У Ивана на телефоне есть \(n\) песен. Размер \(i\)-й песни \(a_i\) байт. У Ивана также есть флеш-карта, которая может хранить не более \(m\) байт информации. Изначально его флеш-карта пустая.

Иван хочет записать все \(n\) песен на свою флеш-карту. Он может сжимать некоторые из них. Если он сжимает \(i\)-ю песню, размер \(i\)-й песни уменьшается с \(a_i\) до \(b_i\) байт (\(b_i < a_i\)).

Иван может сжать любое подмножество песен (возможно, пустое) и записать все песни на флеш-карту, если сумма их размеров не превышает \(m\). Он может сжимать любое подмножество песен (не обязательно подряд идущих).

Иван хочет найти минимальное количество песен, которое необходимо сжать, чтобы все песни поместились на флеш-карте (то есть сумма их размеров была меньше либо равна \(m\)).

Если невозможно записать все песни (даже если Иван сожмет все песни, которые у него есть), выведите «-1». Иначе выведите минимальное количество песен, которое Ивану необходимо сжать.

В комитете по стандартизации собачек паника — щенки из нового выводка умудрились родиться разноцветными! Всего в природе существует 26 различных цветов щенков и они обозначаются буквами от 'a' до 'z' включительно.

Свод правил комитета запрещает даже малейшие отличия между щенками, а потому сотруднику Славе поручили перекрасить часть щенков в другие цвета, тем самым устранив досадные расхождения. К сожалению, излишняя бюрократия и ограниченный бюджет привели к тому, что перекрашивать щенков можно лишь одним образом: выбрать цвет \(x\) такой, что на текущий момент существуют хотя бы два щенка цвета \(x\) (иначе это будет признано нецелевыми расходами), и перекрасить всех щенков цвета \(x\) в произвольный цвет \(y\). По счастью, операцию покраски можно применять неограниченное количество раз (в том числе нулевое).

Например, если количество щенков равно \(7\) и их цвета характеризуются строкой «abababc», то за одну операцию Слава может получить последовательности «zbzbzbc», «bbbbbbc», «aaaaaac», «acacacc» и другие. Однако, если текущая последовательность цветов равна «abababc», то выбрать \(x\)='c' прямо сейчас он не может, так как прямо сейчас только один щенок имеет цвет 'c'.

Помогите Славе и комитету понять, можно ли стандартизировать щенков, покрасив их всех в один цвет.

Заданы \(n\) отрезков на числовой прямой; границы каждого отрезка имеют целочисленные координаты. Некоторые отрезки могут вырождаться в точки. Отрезки могут пересекаться, вкладываться друг в друга или даже совпадать.

Пересечение некоторой последовательности отрезков — это такое максимальное по включению множество точек (не обязательно имеющих целые координаты), что каждая точка лежит внутри каждого отрезка из последовательности. Если полученное множество не пусто, то оно всегда образует некоторый непрерывный отрезок. Длина пересечения — это длина полученного отрезка, либо \(0\), если пересечение — пустое множество.

Например, пересечение отрезков \([1;5]\) и \([3;10]\) — это \([3;5]\) (длина \(2\)), пересечение отрезков \([1;5]\) и \([5;7]\) — это \([5;5]\) (длина \(0\)) и пересечение отрезков \([1;5]\) и \([6;6]\) — это пустое множество (длина \(0\)).

Ваша задача — удалить ровно один отрезок из заданной последовательности таким образом, чтобы пересечение оставшихся \((n - 1)\) отрезков имело максимальную длину.

У каждого из игроков A и B есть по списку, по \(n\) целых чисел в каждом. Они оба хотят максимизировать разность между своими очками и очками соперника.

За один ход, игрок может либо добавить к своим очкам любой элемент из своего списка (если его список не пуст), затем этот элемент удаляется из списка. Или удалить элемента из списка его оппонента (если список его оппонента не пуст).

В случае если в списке есть несколько одинаковых элементов, только один из них будет задействован в какой-то операции. Например, если список состоит из элементов \(\{1, 2, 2, 3\}\) и вы решили выбрать \(2\) для следующего хода, только один экземпляр \(2\) будет удалён (и добавлен к очкам, если это требуется).

Игру начинает игрок А и игра заканчивается когда оба списка становятся пустыми. Найдите разницу между очками A и B, если оба игрока играют оптимально.

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

В магазине компьютерной техники ночью произошла кража.

До этого все клавиатуры, которые продавались в магазине, были пронумерованы по очереди, начиная с некоторого натурального числа \(x\). Например, если \(x = 4\) и в магазине продавалось \(3\) клавиатуры, то они имели номера \(4\), \(5\) и \(6\), а если \(x = 10\) и в магазине продавалось \(7\) клавиатур, то они имели номера \(10\), \(11\), \(12\), \(13\), \(14\), \(15\) и \(16\).

После кражи в магазине осталось \(n\) клавиатур с номерами \(a_1, a_2, \dots, a_n\). Определите минимальное количество клавиатур, которые могли быть украдены, если никто из сотрудников магазина не помнит значение \(x\).

Зиби является тренером команд по спортивному программированию. Всего есть \(n\) участников, которые хотят хорошо подготовиться к соревнованиям. Тренировочные контесты весьма необычны: в каждой команде есть ровно два человека, две задачи, и каждый участник будет писать ровно одну из них. Разумеется, два человека в одной команде будут писать разные задачи.

Правила оценки тоже весьма необычны. Первая задача всегда задача на реализацию: нужно реализовать один весьма известный алгоритм и оценивается время и скорость его написания. Вторая задача — ужасная задача на геометрию, которую нужно сдать хотя бы за какое-нибудь разумное время. Здесь оценивается длина и сложность кода. После этого Зиби даёт некоторые штрафные очки каждому решению (возможно, отрицательные) и итоговый результат команды равен их сумме (чем меньше сумма, тем лучше).

Мы знаем, что \(i\)-й участник наберёт ровно \(x_i\) очков, если будет писать первую задачу, и ровно \(y_i\), если будет писать вторую. Можно считать, что все участники знают способности друг друга и во время контеста распределят задачи таким образом, чтобы минимизировать их итоговый счёт. Напомним, каждый участник напишет ровно одну задачу за контест.

Зиби хочет, чтобы все участники написали тренировочный контест друг с другом. Однако есть \(m\) пар участников, которые ни за что не хотят писать контест вместе. Тем не менее, тренер собирается провести тренировочный контест для всех возможных пар участников, которые не ненавидят друг друга. Для каждого участника тренеру интересно, какова будет сумма очков команд, в которых он примет участие.

Если вы подумали, что Аркадий немного старомоден, так как играет в шашки, то вы не правы. Аркадий и его друзья также любят одну из современных компьютерных игр. Мы не будем обсуждать ее правила, для этой задачи важно лишь то, что каждый игрок должен в начале игры выбрать себе одного героя.

Всего есть \(2\) команды по \(n\) игроков и \(2n\) героев, которых нужно распределить по игрокам. Команды по очереди выбирают героев: сначала первая команда выбирает одного героя в свою команду, затем вторая команда выбирает одного героя себе и так далее. Обратите внимание, что после того, как герой выбран, его больше не может выбрать ни та, ни другая команда.

Друзья оценивают силу \(i\)-го героя как \(p_i\). Каждая команда хочет максимизировать суммарную силу своих героев. Однако, есть одно исключение: есть \(m\) пар героев, которые особенно сильны друг против друга, поэтому когда одна команда выбирает героя из пары, другая команда на своем ходу обязана выбрать другого героя из пары. Каждый герой входит максимум в одну такою пару.

Это — интерактивная задача. Вам нужно написать программу, которая будет оптимально выбирать героев в одну команду, в то время как программа жюри будет играть за другую команду. Обратите внимание, что программа жюри может играть не оптимально, в таком случае вам необходимо использовать шанс и все равно максимизировать суммарную силу своей команды. Формально, если в какой-то момент у вас есть возможность набрать суммарную силу героев в \(q\) или больше, независимо от дальнейших ходов программы жюри, вы должны набрать \(q\) или больше для того, чтобы пройти тест.

Когда очередь ходить ваша, выведите одно целое число \(x\) (\(1 \le x \le 2n\)) — индекс героя, которого вы выбираете. Обратите внимание, вы не можете выбрать героя, которого ранее выбрали вы либо другой игрок, и вы должны следовать правилу о специальных парах героев.

Когда очередь ходить вашему сопернику, считайте одно целое число \(x\) (\(1 \le x \le 2n\)) — индекс героя, выбранного другой командой. Гарантируется, что выбранный герой не будет выбран ранее; гарантируется, что соперник будет следовать правилу о специальных парах героев.

После последнего хода вы должны завершиться, не выводя ничего.

После вывода хода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Ход жюри \(-1\) означает, что ваша программа сделала некорректный ход. Ваша программа должна немедленно завершиться после прочтения ответа \(-1\), вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

Вы пришли на выставку и один экспонат привлёк ваше внимание. Он состоит из \(n\) колонн, где \(i\)-я колонна состоит из \(a_i\) блоков стоящих на полу.

Высота экспоната равна \(m\), а значит количество блоков в каждой колонне не превосходит \(m\).

На потолке есть камера, которая снимает вид экспонат сверху, а также ещё одна камера расположена сбоку и снимает боковой вид этого экспоната.

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

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

Пало-Алто — необычный город, ведь он представляет собой бесконечную координатную прямую. Он известен еще тем, что там находится офис Lyft Level 5.

Lyft стал настолько популярным, что его сейчас используют все \(m\) таксистов в городе, которые каждый день подвозят остальных жителей города — \(n\) пешеходов.

Каждый житель (включая таксистов) Пало-Алто живёт в точке с уникальной координатой (нет такой пары жителей, что их координата одинаковая).

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

Однажды утром таксистам стало интересно: а сколько же есть людей, от которых они могут получить первый вызов в этот день? Другими словами, надо для каждого таксиста \(i\) найти число \(a_{i}\) — количество пешеходов, для которых \(i\)-й таксист — ближайший, или, если таких таксистов несколько, имеет среди таковых наименьшую координату.

Таксист не может подвезти самого себя или других таксистов.

Поликарп подготовил \(n\) задач по программированию, \(i\)-я задача имеет тему \(a_i\). Темы задач могут совпадать.

Поликарп планирует провести серию тематических контестов. Задачи каждого из контестов будут полностью на какую-то одну тему, и темы всех контестов должны быть попарно различны. Он может использовать не все подготовленные задачи. Допустимо, что на какие-то темы не будут проведены контесты.

Поликарп проведет контесты в несколько последовательных дней, по одному контесту в день. Он хочет провести контесты так, чтобы выполнялись условия:

• количество задач в каждом контесте было ровно вдвое больше количества задач в предыдущем контесте (т.е. день назад), количество задач в первом контесте может быть любым;
• общее суммарное количество задач во всех контестах серии должно быть максимально.

Ваша задача найти максимальное суммарное количество задач, которые могут быть использованы в серии тематических контестов. Заметим, что максимизировать количество контестов не надо.

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

Вам дано \(n\) упорядоченных наборов из отрезков. Каждый отрезок может быть представлен как пара целых чисел \([l, r]\), где \(l\leq r\). Каждый набор может содержать произвольное количество отрезков (даже \(0\)), возможно, что некоторые из них будут одинаковыми.

Также у вас есть \(m\) запросов, каждый из которых в виде четырех целых чисел: \(a, b, x, y\). Для каждого запроса вам нужно проверить верно ли, что в каждом наборе с номером \(p\) (\(a\leq p\leq b\)), есть хотя бы один отрезок \([l, r]\), что целиком лежит на отрезке \([x, y]\), то есть \(x\leq l\leq r\leq y\).

Найдите ответ для каждого запроса.

Обратите внимание, что вам нужно решить эту задачу онлайн. То есть, вы получите новый запрос только после того, как ответите на предыдущий.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Мультипредметная олимпиада приближается! Соревнование проводится по \(m\) различным предметам, давая свободу выбора самим участникам. И теперь Александру (тренеру) необходимо собрать делегацию для поездки на олимпиаду среди своих воспитанников.

У Александра на выбор есть \(n\) кандидатов. Для \(i\)-го человека Алекс знает предмет \(s_i\) на котором данный кандидат специализируется и \(r_i\) — уровень его навыка в данной специализации (этот уровень даже может быть отрицательным!).

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

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

(Конечно, у Александра нет лишних денег, поэтому все выбранные делегаты должны участвовать в олимпиаде).

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

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

В университете учатся \(n\) студентов. Количество студентов четно. Умение \(i\)-го студента программировать равно \(a_i\).

Тренер хочет сформировать \(\frac{n}{2}\) команд. Каждая команда должна состоять ровно из двух студентов, а каждый студент должен принадлежать ровно одной команде. Два студента могут сформировать команду только тогда, когда их умение программировать одинаково (иначе они не смогут понять друг друга и не смогут сформировать команду).

Студенты могут решать задачи, чтобы улучшать их умение программировать. Одна решенная задача увеличивает умение программировать на один.

Тренер хочет знать, какое минимальное количество задач студентам необходимо решить, чтобы сформировать ровно \(\frac{n}{2}\) команд (то есть каждая пара студентов должна формировать команду). Ваша задача — найти это количество.

Задано \(n\) отрезков \([l_i, r_i]\) для всех \(1 \le i \le n\). Ваша задача — разделить все отрезки на две непустые группы таким образом, чтобы не существовало пары отрезков из разных групп, имеющих хотя бы одну общую точку, или же сказать, что это сделать невозможно. Каждый отрезок должен принадлежать ровно одной из групп.

Чтобы оптимизировать процесс тестирования, будет дан мультитест.

Дан массив \(a\), состоящий из \(n\) целых чисел. Назовем монотонной перенумерацией массива \(a\) такой массив \(b\), состоящий из \(n\) целых чисел, что выполняются все следующие условия:

• \(b_1 = 0\);
• для каждой пары индексов \(i\) и \(j\), такой, что \(1 \le i, j \le n\), если \(a_i = a_j\), то \(b_i = b_j\) (обратите внимание: если \(a_i \ne a_j\), все равно возможно \(b_i = b_j\));
• для каждого индекса \(i \in [1, n - 1]\) либо \(b_i = b_{i + 1}\), либо \(b_i + 1 = b_{i + 1}\).

Например, если \(a = [1, 2, 1, 2, 3]\), то две монотонные перенумерации \(a\) — следующие: \(b = [0, 0, 0, 0, 0]\) и \(b = [0, 0, 0, 0, 1]\).

Посчитайте количество различных монотонных перенумераций \(a\). Ответ может быть большим, поэтому выведите его остаток от деления на \(998244353\).

Вы играете в новую часть знаменитого файтинга: Kortal Mombat XII. Вы хотите совершить brutality на персонаже вашего противника.

Вы играете в игру на консоли нового поколения, поэтому на вашем геймпаде есть \(26\) кнопок. На каждой кнопке записана строчная буква латинского алфавита от 'a' до 'z'. Все буквы на кнопках попарно различны.

Вам задана последовательность ударов, \(i\)-й удар наносит \(a_i\) единиц урона персонажу противника. Чтобы совершить \(i\)-й удар, вам необходимо нажать кнопку \(s_i\) на вашем геймпаде. Удары пронумерованы от \(1\) до \(n\).

Вы знаете, что если вы нажмете какую-то кнопку больше, чем \(k\) раз подряд, то она сломается. Вы очень дорожите своим геймпадом и не хотите ломать никакую из его кнопок.

Чтобы совершить brutality, вам необходимо нанести некоторые удары из заданной последовательности. Вы можете пропустить любой из них, но менять изначальный порядок ударов вам запрещено. Суммарный нанесенный урон равен сумме \(a_i\) по всем \(i\) среди ударов, которые не были пропущены.

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

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

У вас есть длинная палка, состоящая из \(m\) отрезков, пронумерованных от \(1\) до \(m\). Каждый отрезок имеет длину равную \(1\) сантиметру. Однако, некоторые отрезки сломались и требуют починки.

У вас также есть бесконечно-длинная ремонтная лента. Вы хотели бы вырезать несколько кусочков из этой ленты так, чтобы покрыть все сломанные отрезки. В частности, если разместить кусок ленты целой длины \(t\) в позиции \(s\), то отрезки \(s, s+1, \ldots, s+t-1\) окажутся покрытыми.

Разрешается покрывать не сломанные отрезки, также допускается, что какие-то кусочки ленты будут пересекаться.

Как говорится, время — деньги, поэтому вы хотите покрыть все сломанные отрезки, вырезав не более \(k\) кусочков ленты. Какую минимальную суммарную длину этих кусочков нужно вырезать?

Массив \(b\) называется подмассивом массива \(a\), если он образует непрерывный подотрезок \(a\), то есть равен \(a_l\), \(a_{l + 1}\), \(\ldots\), \(a_r\) для некоторых \(l, r\).

Пусть \(m\) — некоторая зафиксированная константа. Для любого массива, содержащего хотя бы \(m\) элементов, определим его симпатичность, как сумму \(m\) наибольших элементов этого массива. Например:

• Если массив \(x = [4, 3, 1, 5, 2]\) и \(m = 3\), то \(3\) наибольших элемента \(x\) равны \(5\), \(4\) и \(3\), тем самым симпатичность \(x\) равна \(5 + 4 + 3 = 12\).
• Если массив \(x = [10, 10, 10]\) и \(m = 2\), то симпатичность \(x\) равна \(10 + 10 = 20\).

Вам дан массив \(a_1, a_2, \ldots, a_n\), значение константы \(m\) и целое число \(k\). Вам нужно разбить массив \(a\) на ровно \(k\) подмассивов таких, что:

• Каждый элемент \(a\) принадлежит ровно одному подмассиву.
• Каждый подмассив содержит хотя бы \(m\) элементов.
• Суммарная симпатичность всех \(k\) подмассивов в разбиении является наибольшей возможной.

Недавно Алена купила миниатюрный холодильник, который может быть представлен как таблица из \(h\) строк и \(2\) столбцов. Изначально в холодильнике лишь одна полка в самом низу, но Алена может установить любое число полок внутрь холодильника между любыми двумя рядами. Все полки имеют ширину в две клетки, не занимают места по вертикали, но разделяют холодильник на верхнюю и нижнюю части.

Пример холодильника с \(h = 7\) и двумя полками. Полки показаны черным. Рисунок соответствует первому примеру.

У Алены есть \(n\) бутылок молока, она хочет поставить их в холодильник. Высота \(i\)-й бутылки равна \(a_i\) клеток, а ширина любой бутылки равна \(1\) клетке. Алена может поставить бутылку на полку, если высота свободного пространства над этой полкой не меньше высоты бутылки. Она не может ставить бутылки друг на друга (если, конечно, между ними нет полки). Бутылки не могут занимать общие клетки в таблице.

Алена хочет найти максимальное целое число \(k\) такое, что она может одновременно поставить бутылки с номерами \(1\), \(2\), ..., \(k\) в холодильник. Найдите это наибольшее \(k\).

В азбуке Морзе каждая буква латинского алфавита определена как строка некоторый длины от \(1\) до \(4\), состоящая из точек и тире. В этой задаче мы будем обозначать точку как «0», а тире как «1».

Так как существует \(2^1+2^2+2^3+2^4 = 30\) строк длины от \(1\) до \(4\), состоящих только из «0» и «1», не все из них соответствуют какой-то из \(26\) букв латинского алфавита. А именно, все строки из «0» и/или «1» длины не более \(4\) соответствуют разным буквы латинского алфавита, кроме следующих четырех строк, которые ничему не соответствуют: «0011», «0101», «1110» и «1111».

Вы работаете на строке \(S\), которая изначально пуста. \(m\) раз далее либо точка, либо тире будут дописаны к \(S\), по одному символу за раз. Ваша задача — после каждого добавления к строке \(S\) найти количество непустых последовательностей букв латинского алфавита, которые представляются в азбуке Морзе как некоторая подстрока \(S\).

Так как ответы могут быть очень большим, выводите их по модулю \(10^9 + 7\).

Вы зашли в ближайший магазин, чтобы купить несколько плиток шоколада. В магазине продаются \(n\) плиток, \(i\)-я стоит \(a_i\) монет (и вы хотите купить их все).

У вас есть \(m\) разных купонов, позволяющих покупать шоколадки на особых условиях. \(i\)-й купон позволяет купить \(q_i\) шоколадок, при этом заплатив только за \(q_i - 1\) наиболее дорогих из них (то есть самая дешевая из \(q_i\) шоколадок вам достанется бесплатно).

Вы можете использовать только один купон; если вы используете купон \(i\), вы должны выбрать \(q_i\) шоколадок, которые вы купите по купону, а все остальные \(n - q_i\) плиток вы купите без каких-либо скидок.

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

Вы — университетский тренер. Всего в университете \(n\) студентов под Вашим надзором, умение программировать \(i\)-го студента равно \(a_i\).

Вы хотите составить \(k\) команд для другого нового соревнования по программированию. Как Вы знаете, чем больше студентов на соревновании — тем больше шансов победить! Поэтому Вы хотите составить не более \(k\) непустых команд (и хотя бы одну) таким образом, чтобы суммарное число студентов в них было максимально возможно. Но Вы также знаете, что каждая команда должна быть сбалансированной. Это означает, что умение программировать каждой пары студентов в каждой команде должно отличаться не более, чем на \(5\). Команды являются независимыми друг от друга (это означает, что разница в умении программировать двух студентов из двух разных команд не имеет значения).

Возможно, что некоторые студенты не будут включены ни в какие команды вообще.

Ваша задача — найти максимально возможное суммарное число студентов в не более, чем \(k\) (и хотя бы одной) непустых сбалансированных командах.

Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

Даша очень любит приключения. На днях ей встретился удивительный город, представляющий из себя \(n\) улиц, направленных вдоль восточного направления, и \(m\) улиц, направленных вдоль южного направления, образующих естественным образом \(nm\) перекрестков. На любом пересечении \(i\)-й улицы, идущей на восток, и \(j\)-й улицы, идущей на юг, можно увидеть монументальной величины небоскреб. Загоревшись любопытством, Даша решила исследовать высоту городских строений.

Проходя через перекресток на пересечении \(i\)-й и \(j\)-й улицы соответствующих направлений, Даша оглядывает две улицы, на которых находится. Узнав высоты всех небоскрёбов, которые находятся на этих двух улицах, Даша задаётся вопросом: как можно переназначить высоты всем небоскрёбам на этих двух улицах, чтобы максимальная высота была как можно меньше, а результат сравнения высот у любых двух небоскрёбов на одной улице не изменился.

Сформулируем задачу формально. На каждом из \(nm\) перекрёстков Даша независимо от других перекрёстков решает задачу. Сейчас она видит \(n + m - 1\) небоскрёбов, и для каждого видит его настоящую высоту. При этом любые два небоскрёба можно сравнить по высоте и получить результат «больше», «меньше» или «равно». Теперь Даша хочет выбрать некоторое целое \(x\), после чего назначить каждому небоскрёбу целую положительную высоту от \(1\) до \(x\). При назначении высот Даша хочет сохранить относительный порядок в каждой из улиц. То есть результат сравнения высоты любых двух небоскрёбов на текущей улице восточного направления не должен измениться, и результат сравнения высоты любых двух небоскрёбов на текущей улице южного направления не должен измениться. При этом небоскрёбы, находящиеся только на текущей улице восточного направления не сравниваются с небоскрёбами, находящими на текущей улице южного направления, а небоскрёб, находящийся на пересечении, может сравниваться и с теми и с теми. Для каждого перекрёстка Даша хочет независимо вычислить минимальное возможное подходящее \(x\).

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

То можно заменить высоты небоскрёбов следующим образом (заметим, что все сравнения на меньше, больше или равно внутри улицы южного направления и внутри улицы восточного направления при этом не поменяются).

Наибольшее использованное число равно \(5\), а значит ответом для этого перекрёстка было бы \(5\).

У Поликарпа есть массив \(a\), состоящий из \(n\) целых чисел.

Он хочет поиграть в игру с этим массивом. Игра состоит из нескольких шагов. Во время первого хода он выбирает любой элемент и удаляет его (после первого хода массив содержит \(n-1\) элемент). Для каждого из следующих ходов он выбирает любой элемент с одним ограничением: его четность должна отличаться от четности элемента, удаленного во время прошлого хода. Другими словами, он меняет четности (четный-нечетный-четный-нечетный-... или нечетный-четный-нечетный-четный-...) удаляемых элементов. Поликарп останавливается, если не может совершить ход.

Формально:

• Если сейчас первый ход, он выбирает элемент и удаляет его;
• Если это второй или любой следующий ход:
  • если последний удаленный элемент был нечетным, Поликарп выбирает любой четный элемент и удаляет его;
  • если последний удаленный элемент был четным, Поликарп выбирает любой нечетный элемент и удаляет его.
• Если после какого-то хода Поликарп не может сделать ход, игра заканчивается.

Цель Поликарпа — минимизировать сумму неудаленных элементов массива после конца игры. Если Поликарп может удалить массив целиком, тогда сумма неудаленных элементов равна нулю.

Помогите Поликарпу найти это значение.

Вам дана перестановка \(p\) целых чисел от \(1\) до \(n\), где \(n\) чётно.

Вы хотите отсортировать перестановку. Для этого вы можете проделать ноль и более операций следующего вида:

• выбрать два индекса \(i\) и \(j\), такие что \(2 \cdot |i - j| \geq n\), и поменять \(p_i\) и \(p_j\).

Вы хотите отсортировать перестановку за не более чем \(5 \cdot n\) операций. Можно показать, что это всегда можно сделать. Обратите внимание, что не требуется минимизировать число операций.

На числовой прямой расположены \(n\) камней. Изначально \(i\)-й камень находится в точке с координатой \(s_i\). В одной точке может находиться более одного камня одновременно.

Вы можете выполнить ноль или более операций следующего вида:

• взять два камня с индексами \(i\) и \(j\) такими, что \(s_i \leq s_j\), выбрать целое число \(d\) (\(0 \leq 2 \cdot d \leq s_j - s_i\)) и заменить координату \(s_i\) на \((s_i + d)\), а координату \(s_j\) на \((s_j - d)\). Другими словами, подвинуть камни друг к другу.

Вы хотите подвинуть камни так, чтобы они находились в позициях \(t_1, t_2, \ldots, t_n\). Порядок камней не важен — требуется лишь, чтобы мультимножество координат камней в конце совпадало с мультимножеством, состоящим из \(t_1, t_2, \ldots, t_n\).

Выясните, возможно ли сдвинуть камни требуемым образом, и если да, то найдите способ это сделать. Минимизировать число операций не нужно.

На перемене в буфете научного лицея Королевства Кремляндия образовалась очередь из \(n\) лицеистов, пронумерованных от \(1\) до \(n\). Изначально каждый ученик \(i\) стоит на позиции \(i\). Каждый ученик \(i\) характеризуется двумя числами — \(a_i\) и \(b_i\). Недовольство лицеиста \(i\) равняется произведению \(a_i\) на количество людей, стоящих слева от его позиции, прибавить произведение \(b_i\) на количество людей, стоящих справа от его позиции. Формально, недовольство ученика \(i\), который стоит на позиции \(j\), равняется \(a_i \cdot (j-1) + b_i \cdot (n-j)\).

Директор поручил Стасу задание: переставить людей в очереди так, чтобы минимизировать суммарное недовольство.

Хоть Стас и умеет решать подобные задачи, но эта ему не далась. Он обратился за помощью к вам.

В магазине поблизости продается \(n\) лопат. \(i\)-я лопата стоит \(a_i\) бурлей.

Миша хочет купить ровно \(k\) лопат. EКаждая лопата может быть куплена не более одного раза.

Миша может покупать лопаты в несколько покупок. В течение одной покупки он выбирает любое подмножество оставшихся (еще не купленных) лопат и покупает это подмножество.

Также в магазине есть \(m\) специальных предложений. \(j\)-е из них задано парой \((x_j, y_j)\) и означает, что если Миша купит ровно \(x_j\) лопат в течение одной покупки, то \(y_j\) самых дешевых из них он получит бесплатно (то есть он не будет платить за \(y_j\) самых дешевых лопат в течение текущей покупки).

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

Ваша задача — посчитать минимальную стоимость покупки \(k\) лопат, если Миша будет покупать их оптимальным образом.

Задана строка, состоящая из строчных латинских букв.

Пара соседних букв в строке считается противной, если данные буквы так же соседние в алфавите. Например, строка «abaca» содержит противные пары на позициях \((1, 2)\) — «'ab» и \((2, 3)\) — «ba». Буквы 'a' и 'z' не считаются соседними в алфавите.

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

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

Также требуется ответить на \(T\) независимых запросов.

На праздник пришло \(n\) мальчиков и \(m\) девочек. Каждый мальчик подарил каждой девочке некоторое целое количество конфет (возможно ноль). Пронумеруем мальчиков целыми числами от \(1\) до \(n\) и девочек целыми числами от \(1\) до \(m\). Для всех \(1 \leq i \leq n\) минимальное количество конфет, которое подарил мальчик с номером \(i\) какой-то девочке равно \(b_i\) и для всех \(1 \leq j \leq m\) максимальное количество конфет, которое получила девочка с номером \(j\) от какого-то мальчика равно \(g_j\).

Более формально, Обозначим за \(a_{i,j}\) количество конфет, которое \(i\)-й мальчик подарил \(j\)-й девочке. Тогда \(b_i\) равно минимуму среди значений \(a_{i,1}, a_{i,2}, \ldots, a_{i,m}\) И \(g_j\) равно максимуму среди значений \(b_{1,j}, b_{2,j}, \ldots, b_{n,j}\).

Вам стало интересно, какое минимальное суммарное количество конфет могли подарить мальчики, то есть вы хотите минимизировать сумму \(a_{i,j}\) по всем таким \((i,j)\), что \(1 \leq i \leq n\) и \(1 \leq j \leq m\). По числам \(b_1, \ldots, b_n\) и \(g_1, \ldots, g_m\) определите это число.

Поликарп хочет потренироваться перед очередным важным соревнованием по программированию. В течение первого дня его тренировок он хочет решить ровно \(1\) задачу, в течение второго дня — ровно \(2\) задачи, в течение третьего дня — ровно \(3\) задачи, и так далее. В течение \(k\)-го дня он хочет решить ровно \(k\) задач.

У Поликарпа есть список из \(n\) контестов, \(i\)-й контест состоит из \(a_i\) задач. В течение каждого дня Поликарп будет выбирать ровно один из контестов, который он еще не решал до этого, и решать его. Он решает ровно \(k\) задач из этого контеста. Остальные задачи исключаются из контеста. Если контестов, состоящих из не менее \(k\) задач, которые Поликарп еще не решал, в течение \(k\)-го дня нет, то Поликарп прекращает тренироваться.

Как много дней Поликарп сможет тренироваться, если будет выбирать контесты оптимально?

В легенде об образовании Векторляндии говорится о двух целых числах \(x\) и \(y\). Несколько веков назад король массивов поставил две отметки в точки \(|x|\) и \(|y|\) на числовой прямой, захватил всю землю между ними (включая границы) и назвал ее Массивляндией. Спустя много лет король векторов поставил две отметки в точки \(|x - y|\) и \(|x + y|\), захватил всю землю между ними (включая границы) и назвал ее Векторляндией. Все знают, что вся земля Массивляндии лежала внутри или на границе Векторляндии.

Выражение \(|z|\) обозначает абсолютное значение числа \(z\).

На экзамене по истории Жозе попался следующий вопрос: «Каковы значения \(x\) и \(y\)?». Жозе не знает ответа на этот вопрос, но он думает, что сузил количество вариантов ответа до \(n\) целых чисел \(a_1, a_2, \dots, a_n\). Он хочет узнать число таких неупорядоченных пар двух различных чисел из этих \(n\), что легенда могла быть верной, если \(x\) и \(y\) были равны этим числам. Возможно также, что Жозе неправ и никакая пара чисел не удовлетворяет легенде.

Вам дан массив \(a\) длины \(2n\). Возможно ли поменять числа местами так, чтобы сумма первых \(n\) чисел не была равна сумме последних \(n\) чисел?

Вам заданы массив \(a_1, a_2, \dots, a_n\) и число \(k\).

Вам нужно разделить массив на \(k\) непустых последовательных подотрезков. Каждый элемент в массиве должен быть покрыт ровно одним подотрезком. Пусть \(f(i)\) равно индексу подотрезка, которому принадлежит \(i\)-й элемент. Подотрезки нумеруются слева направо и от \(1\) до \(k\).

Тогда цена конкретного разбиения будет равна \(\sum\limits_{i=1}^{n} (a_i \cdot f(i))\). Например, если \(a = [1, -2, -3, 4, -5, 6, -7]\), и мы разделили его на \(3\) подотрезка следующим способом: \([1, -2, -3], [4, -5], [6, -7]\), тогда цена разбиения будет равна \(1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9\).

Посчитайте максимальную цену, которую вы можете получить, разделив массив \(a\) на \(k\) непустых последовательных подотрезков.

Вы играете в компьютерную игру, которая называется Splay the Sire. Сейчас Вы сражаетесь с финальным боссом игры.

Битва с боссом состоит из \(n\) ходов. В течение каждого хода Вы получаете некоторое количество карт. Каждая карта имеет два параметра: ее цену \(c_i\) и урон \(d_i\). Вы можете играть какими-то картами в какой-то последовательности в течение каждого хода (Вы выбираете карты и точный порядок, в котором их поставите) до тех пор, пока суммарная стоимость карт, которыми Вы играете в течение хода, не превосходит \(3\). После игры некоторым (возможно, нулевым) количеством карт Вы заканчиваете ход, а все карты, которыми Вы не сыграли, пропадают. Заметьте, что вы можете использовать каждую карту не более одного раза.

Ваш персонаж также нашел артефакт, который позволяет увеличить урон некоторых действий: каждая \(10\)-я карта, которую Вы играете, наносит двойной урон.

Чему равен максимально возможный урон, который Вы можете нанести в течение \(n\) ходов?

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

Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть \(m\) городов, пронумерованных от \(1\) до \(m\), готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые \(n\) лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

Эта задача отличается от предыдущей только ограничениями.

На летние каникулы Петя приехал в Байтландию. Как оказалась, история этого государства весьма необычна.

Изначально, до появления Байтландии, на её территории были расположены \(n\) различных стран. Каждое государство владело своей территорией, которую можно было представить на карте как прямоугольник, стороны которого параллельны осям координат, а вершины расположены в целочисленных точках. Никакие две страны не пересекались, однако они могли касаться сторонами. Иногда в результате агрессивных переговоров и мирных военных походов две страны объединялись в одну. Слияние происходило только в том случае, если после объединения их владений снова получалась прямоугольная территория. В конце концов осталось только одно государство — Байтландия.

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

Возможное формирование Байтландии. Замки отмечены синим цветом.

Петя не смог смириться с тем, что не осталось никаких данных об изначальных странах. У него возникло подозрение, что вся эта история всего лишь вымысел. Он знает, что вы умный человек, и поэтому просит у вас помощи. Требуется выяснить, существует ли расположение изначальных государств, для которых может быть верна данная история, или нет.

Скоро на самой известной платформе по программированию (Topforces) будет проходить очень важное соревнование!

У авторов есть набор из \(n\) задач и они должны выбрать не более трех из них в контест. Красота \(i\)-й задачи равна \(a_i\). Авторы хотят составить самый красивый контест (другими словами, суммарная красота выбранных задач должна быть максимально возможной).

Но в подготовке контеста есть одна очень важная особенность: из-за некоторых предрассудков авторов красоты задач не могут делить друг друга. Иными словами, если красоты выбранных задач равны \(x, y, z\), тогда \(x\) не должен делиться ни на \(y\), ни на \(z\), \(y\) не должен делиться ни на \(x\), ни на \(z\) и \(z\) не должен делиться ни на \(x\), ни на \(y\). Если красоты выбранных задач равны \(x\) и \(y\), то \(x\) должен не делиться на \(y\) и \(y\) должен не делиться на \(x\). Любой контест, составленный из одной задачи, является хорошим.

Ваша задача — найти максимально возможную суммарную красоту контеста, составленного из не более трех задач из заданного набора.

Вам необходимо ответить на \(q\) независимых запросов.

Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

Хайди и Доктор Кто выскочили из ТАРДИС и обнаружили себя в EPFL в 2018 году. Они были окружены штормовиками, и к ним приближался Дарт Вейдер. Каким-то чудом им удалось сбежать на ближайшую базу повстанцев, но Доктор был сильно смущён происходящим. Хайди напомнила ему, что в прошлом году основной темой HC2 были Звёздные Войны. После чего Доктор всё понял и приготовился встретиться лицом к лицу со злом Империи.

У повстанцев было \(s\) космических кораблей, каждый с некоторой силой атаки \(a\).

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

У Империи есть \(b\) баз, каждая с некоторой силой защиты \(d\) и некоторым количеством золота \(g\).

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

Если космический корабль атакует базу, то он похищает всё золото, которое там находилось.

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

Единственное отличие этой версии от усложнённой — это ограничения.

В Берляндском государственном университете началась сессия. Многие студенты уже сдают экзамены.

Совсем скоро Полиграф Полиграфович примет экзамен у группы из \(n\) студентов. Студенты будут сдавать экзамен подряд один за другим в порядке от \(1\)-го до \(n\)-го. Процесс сдачи происходит следующим образом:

• \(i\)-й студент подходит к преподавательскому столу и тянет билет;
• если студент понимает, что билет для него слишком сложный, то он отказывается отвечать и уходит домой (этот процесс происходит настолько быстро, что считается, что на него не расходуется время);
• если студент посчитал, что билет несложный, то он тратит ровно \(t_i\) минут на сдачу экзамена, после чего он получает отметку и уходит домой.

Студенты сдают экзамен один за другим без перерывов. Полиграф Полиграфович в один момент времени принимает экзамен у одного студента.

Длительность всего экзамена составляет \(M\) минут (\(\max t_i \le M\)), поэтому чем ближе студент находится к концу списка, тем больше вероятность того, что он не успеет сдать экзамен.

Ваша задача состоит в том, чтобы для каждого студента \(i\) определить минимальное количество студентов, которые должны уйти домой, чтобы \(i\)-й студент гарантированно успел полностью сдать экзамен.

Для каждого студента \(i\) ответ надо искать независимо, то есть если при нахождении ответа для студента \(i_1\) про какого-то студента \(j\) выяснилость, что он должен уйти, то при нахождении ответа для \(i_2\) (\(i_2>i_1\)) студент \(j\) не обязательно должен уйти домой.

Вам дано \(n\) чисел \(a_1, a_2, \ldots, a_n\). Возможно ли расставить их по окружности таким образом, чтобы каждое число было строго меньше суммы своих соседей?

К примеру, для массива \([1, 4, 5, 6, 7, 8]\), расстановка слева удовлетворяет условию, в то время как расстановка справа нет, так как \(5\ge 4 + 1\) и \(8> 1 + 6\).

Дано \(n\) точек на плоскости, \(i\)-я из которых расположена в \((x_i, y_i)\). Tokitsukaze хочет нарисовать странную прямоугольную область и взять все точки в этой области.

Странная область ограничена тремя прямыми, \(x = l\), \(y = a\) и \(x = r\), это ее левая, нижняя и правая сторона, соответственно, где \(l\), \(r\) и \(a\) могут являться любыми вещественными числами, удовлетворяющими \(l < r\). Верхняя сторона области неограничена, то есть можно считать, что она ограничена прямой, параллельной оси \(x\), и бесконечно удаленной. Странная прямоугольная область изображена на следующей иллюстрации.

Точка \((x_i, y_i)\) находится в странной прямоугольной области тогда и только тогда, когда \(l < x_i < r\) и \(y_i > a\). К примеру, на иллюстрации выше \(p_1\) находится в области, а \(p_2\) — нет.

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

Сегодня Денис проводит в ЛКШ клуб анонимных геометров. Он заготовил для клуба \(n\) выпуклых многоугольников, пронумерованных от \(1\) до \(n\). Он планирует предложить участникам клуба посчитать суммы Минковского этих многоугольников. А именно, он планирует дать \(q\) заданий, в \(i\)-м из них нужно посчитать сумму Минковского многоугольников с номерами от \(l_i\) до \(r_i\) включительно.

Суммой Минковского двух множеств \(A\) и \(B\) называется множество \(C = \{a + b : a \in A, b \in B\}\). Можно доказать, что если \(A\) и \(B\) являются выпуклыми многоугольниками, то \(C\) тоже будет выпуклым многоугольником.

Сумма двух выпуклых многоугольников

Чтобы посчитать сумму Минковского \(p\) многоугольников (\(p > 2\)), нужно посчитать сумму Минковского первых \(p - 1\) многоугольников, а потом сумму Минковского результата и \(p\)-го многоугольника.

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

Назовем \(k\)-ступенчатой лестницей следующую конструкцию: ровно \(k + 2\) деревянные доски, среди которых

• две доски длиной хотя бы \(k+1\) — основные направляющие лестницы;
• \(k\) досок длиной хотя бы \(1\) — ступеньки лестницы.

Заметим, что ни направляющие, ни ступени не обязаны быть равны.

Например, лестницы \(1\) и \(3\) — корректные \(2\)-ступенчатые лестницы, а лестница \(2\) — корректная \(1\)-ступенчатая. На первом изображении длины досок равны \([3, 3]\) для направляющих и \([1]\) для ступеньки. На втором изображении длины досок равны \([3, 3]\) для направляющих и \([2]\) для ступеньки. На третьем изображении длины досок равны \([3, 4]\) для направляющих и \([2, 3]\) для ступенек.

У вас есть \(n\) досок. Длина \(i\)-й доски равна \(a_i\). У вас нет пилы и вы не можете распиливать доски. Зато есть молоток и гвозди, и вы можете собрать импровизированную «лестницу» из тех досок, что есть.

Вопрос в следующем: чему равно максимальное \(k\) такое, что вы сможете собрать \(k\)-ступенчатую лестницу, используя некоторый поднабор из имеющихся досок?

В магазине неподалеку продаются известные русские деревянные игрушки под названием «матрешки», и вы бы хотели приобрести несколько штук. В магазине продается \(n\) различных матрешек. Любая матрешка — это фигурка объема \(out_i\) с пустотой внутри объемом \(in_i\) (конечно, \(out_i > in_i\)).

У вас не так много свободного места в сумке, но, к счастью, вы знаете, что матрешки можно вкладывать друг в друга. Формально, назовем набор матрешек вкладываемым, если мы можем переупорядочить их таким образом, что первая матрешка вкладывается во вторую, вторая — в третью и так далее. Матрешка \(i\) вкладывается в матрешку \(j\), если \(out_i \le in_j\). Только последняя игрушка из вкладываемого набора будет занимать место в вашей сумке.

Назовем пустотой вкладываемого набора общий объем пустого места внутри данной структуры. Очевидно, что она равна \(in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})\), где \(i_1\), \(i_2\), ..., \(i_k\) — индексы выбранных матрешек в порядке их вкладывания.

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

Вы хотели бы купить много матрешек, а потому выбираете достаточно большой вкладываемый поднабор. Но автора задачи сильно расстроит, если в вашей сумке будет потрачено зря слишком много места, поэтому вы выбираете достаточно большой вкладываемый поднабор, пустота которого минимально возможная среди всех достаточно больших поднаборов. И вот возник вопрос: как много различных поднаборов удовлетворяют всем требованиям (поднаборы достаточно большие, и нет другого достаточно большого поднабора с пустотой меньше заданного). Два поднабора считаются различными, если существует хотя бы один индекс \(i\) такой, что один поднабор содержит \(i\)-ю матрешку, а другой — нет.

Так как ответ может быть очень большим — выведите его по модулю \(10^9 + 7\).

В некотором государстве живёт \(n\) граждан. Количество денег у \(i\)-го из них равно \(a_{i}\). Государство внимательно следит за благосостоянием своих граждан. Если гражданин совершил покупку или заработал денег, то он обязан отправить в социальные службы справку об изменении баланса с указанием текущего количества денег. Иногда государство делает выплаты малоимущим гражданам: всем гражданам, у кого текущее количество денег строго меньше \(x\), выплачивают пособие такого размера, чтобы количество денег у них стало ровно \(x\). В таком случае гражданин не должен отправлять справку о изменении баланса.

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

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

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

—Да это же очень просто! — воскликнул Валера и сразу же выдал сестре ответ.

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

На бал в королевском дворце пришли N дам. Каждая дама характеризуется тремя параметрами: красотой, умом и богатством. Королевский церемониймейстер знает, что дамы — существа особенные. А именно, если какая-то дама видит, что на балу присутствует другая дама, которая умнее, красивее и богаче ее, то она может выброситься с балкона королевского дворца. Ему известны параметры всех дам и он хочет выяснить, сколько в этот вечер будет потенциальных дам-самоубийц. Обозначим красоту i-й дамы за B_i, ум за I_i и размер состояния за R_i. Тогда i-я дама является потенциальной самоубийцей, если для какой-то дамы j выполняется B_i < B_j, I_i < I_j, R_i < R_j. Найдите число потенциальных самоубийц.