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

Москва в представлении Егора представляет собой длинное прямое шоссе, вдоль которого расположено n башен, пронумерованных в порядке их следования числами от 1 до n . Все башни имеют различные высоты, которые выражаются целыми числами от 1 до n . Высота башни с номером i составляет h _i .

Однако Егор не любит возрастающие последовательности. Его разочаровывают тройки башен, таких что с возрастанием их индексов их значения тоже возрастают. Более формально, тройка башен с номерами i , j и k разочаровывает Егора, если i < j < k и h _i < h _j < h _k .

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

Сегодня у Кроша день рождения! По этому поводу он испек огромный торт. Торт представляет собой прямоугольник n × m , разделенный на nm единичных квадратиков горизонтальными и вертикальными линиями из крема.

На праздник в гости к Крошу пришли Совунья и Нюша. По законам гостеприимства, Крош должен поделиться с своим тортом. Для этого он хочет по очереди отрезать от торта два куска и раздать их гостьям.

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

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

Игорь читает новостную ленту в своей любимой социальной сети, состоящую из n последовательно расположенных записей. Каждая запись в ленте имеет свою характеристику — позитивность a _i , заданную натуральным числом. После прочтения i -й записи настроение Игоря улучшается на a _i .

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

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

Скоро у Гарри Поттера день рождения! Гермиона хочет приготовить для него необычный подарок. Она хочет подарить Гарри набор из n волшебных конфет. Каждая конфета характеризуется её вкусом — целым числом t _i . Удовольствие , которое получит Гарри от набора конфет — это сумма вкусов всех конфет в этом наборе. Обратите внимание, что вкусы конфет, как и удовольствие Гарри, не обязательно должны быть положительными.

У Гермионы есть огромная коробка с конфетами, в которой для каждого целого числа t от - 10 ⁹ до 10 ⁹ лежит ровно одна конфета со вкусом t . Гермиона хочет взять из этой коробки n конфет, из которых будет состоять набор для Гарри.

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

Марина очень любит палиндромы. Палиндром — это строка, которая одинаково читается слева направо и справа налево, например « noon », « rotator » или « radar ».

Марина написала на доске строку s , состоящую из n строчных латинских букв s _{1 s 2} ... s _n . Подстрокой строки s называется строка s _{ls l + 1} ... s _r для некоторых 1 ≤ l ≤ r ≤ n . Марина ищет в строке s как можно более длинную подстроку, которая является палиндромом. Например, в строке « rotateradars » такой подстрокой будет « radar ».

Вова хочет изменить написанную Мариной строку, чтобы подстрока-палиндром была как можно длиннее. Он может либо оставить строку нетронутой, либо изменить в ней ровно одну букву на другую. Например, если в строке « rotateradars » изменить шестую букву на « o », получится строка « rotatoradars », в которой максимальная подстрока-палиндром « rotator » имеет длину 7 . Подстроку-палиндром большей длины получить нельзя.

Помогите Вове определить, какую максимальную длину подстроки-палиндрома он сможет получить.