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

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

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

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

Кодовый замок имеет экран, и на этом экране сейчас написана строка $$$s$$$, состоящая из маленьких букв английского алфавита. Любимое слово Вектора — строка $$$t$$$ той же длины, что и строка $$$s$$$. Грю уверен, что замок откроется, когда на экране вместо $$$s$$$ будет отображаться строка $$$t$$$.

Рядом с экраном есть поле для ввода целого числа и одна единственная кнопка. Доктор Нефарио проанализировал это устройство и сообщил Грю и вам, что в поле можно ввести любое целое число от $$$1$$$ до $$$|s|$$$, а при нажатии кнопки

1. строка $$$s$$$ разбивается на префикс $$$p$$$ длины $$$|s| - x$$$ (строку из первых $$$|s| - x$$$ символов $$$s$$$) и суффикс $$$q$$$ длины $$$x$$$ (строку из оставшихся $$$x$$$ символов), где $$$x$$$ — введенное в поле число;
2. и затем $$$s$$$ заменяется на $$$\overline{q^{\mathtt{rev}}p}$$$, то есть на конкатенацию (запись подряд) развернутой строки $$$q$$$ и строки $$$p$$$.

Иными словами, суффикс строки $$$s$$$ длины $$$x$$$ разворачивается и переставляется в начало строки. Например, ввод числа $$$2$$$ и нажатие на кнопку заменит строку «arkshs» на «sharks».

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

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

Кевин (один из миньонов) увлекся рисованием на шестиугольных решетках. Шестиугольной решеткой называется решетка, разбивающая плоскость на равные правильные шестиугольники. Каждый шестиугольник однозначно соответствует паре целочисленных координат, где первая ось координат направлена строго вниз, а вторая — под углом $$$120^\circ$$$ к ней. Рисунок, изображающий решетку и систему координат, можно видеть ниже:

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

Две ячейки называются соседними, если их границы имеют общую сторону. Например, ячейки $$$(1, 3)$$$ и $$$(2, 2)$$$ — соседние, а $$$(1, 3)$$$ и $$$(3, 2)$$$ — нет. Множество ячеек называется связным, если от любой ячейки множества до любой можно «добраться», двигаясь каждый раз в ячейку из множества, соседнюю с предыдущей, и двусвязным, если между любыми двумя ячейками множества существует хотя бы два непересекающихся по ячейкам пути.

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

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

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

В этой задаче всего 43 теста, не считая примеров к условию. Все тесты оцениваются независимо. Если ваш ответ на определенный тест корректен, за этот тест вы получаете $$$$$$\mathtt{score} = \begin{cases} 0 & \text{если } \frac{j}{p} \lt \gamma \\ \mathtt{cost} \cdot \min\left(1, \frac{j}{p}\right) & \text{иначе} \end{cases}$$$$$$ баллов, где $$$\mathtt{cost}$$$ — стоимость теста, $$$p$$$ — количество ячеек, удаляемых в вашем ответе, $$$j$$$ — количество ячеек, удаляемых решением жюри, и $$$\gamma$$$ — нижняя граница на «оптимальность ответа».

Иными словами, если ваш ответ более чем в $$$\gamma^{-1}$$$ раз хуже ответа жюри, вы получаете $$$0$$$ баллов за этот тест. Иначе вы получаете долю от максимального числа баллов за тест, отражающую насколько оптимален ваш ответ в сравнении с ответом жюри.

Миньоны много путешествовали в поисках того, кто сможет стать их новым лидеров, перед тем, как встретились с Грю. Наиолее перспективными были $$$n$$$ городов, $$$i$$$-й из которых, по их оценкам, обладает перспективностью $$$a_{i}$$$.

Разумеется, это не единственный критерий оценки городов. Миньонам также важно весело провести время. При этом посетить город $$$i$$$ можно двумя способами:

1. либо проездом, в случае чего миньоны получают $$$(a_{i} - c)^2$$$ удовольствия от посещения данного города;
2. либо заехав в город на день, и в таком случае миньоны получат $$$(a_{i} - a_{\mathtt{prev}})^2$$$ удовольствия от его посещения, где $$$\mathtt{prev}$$$ — номер последеного города, в котором миньоны находились в течение дня (не проездом).

При этом в случае, когда миньоны в первый раз за всю поездку заезжают на день в какой-то город (пусть это город $$$i$$$), стоит считать $$$a_\mathtt{prev}$$$ равным $$$a_i$$$, и в таком случае они не получают удовольствия от его посещения.

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

При этом в города номер $$$1$$$ и номер $$$n$$$ обязательно заехать на день! Таким образом, удовольствия от посещения первого города они не получат.

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