Петя участвует в конкурсе, в котором разыгрывается \(n\) призов. Призы пронумерованы от 1 до \(n\).

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

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

Требуется написать программу, которая по заданным ценностям призов определяет для каждого \(k\) от 2 до \(n\), приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе \(k\) баллов.

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

Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером \(a \times b\) метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна \(d\) метрам, будет иметь форму прямоугольника размером \((a + 2d) \times (b + 2d)\) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером \(w \times h\) метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

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

Рассмотрим строку \(s\), состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

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

Например, \(W\)(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.

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

Например, \(Y\)(«abba») = \(W\)(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.

Будем называть строку \(s\) странной, если для нее \(W\)(\(s\)) = \(Y\)(\(s\)). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее \(W\)(«abb») = \(Y\)(«abb») = {«a», «b», «ab», «bb», «abb»}.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке \(s\) в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке \(s\) определяет ее странность.

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

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

• каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
• стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
• участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
• суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

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

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

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