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

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

Задана последовательность [ a ₁ , a ₂ , ..., a _n ] . Будем называть отрезок элементов заданной последовательности [ a _l , a _{l + 1} , ..., a _r ] корректным, если он представляет собой корректную последовательность: a _l является минимальным числом на этом отрезке, а a _r — максимальным.

В рамках исследования необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность [2, 3, 1, 1, 5, 1] можно разбить на три корректных отрезка: [2, 3] и [1, 1, 5] и [1] .

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

Скажем, что последовательность строк t ₁ , ..., t _k является путешествием длины k , если для всех i > 1 t _i является подстрокой t _{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t ₁ , ..., t _k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u ₁ , ..., u _{k + 1} , такие, что s = u ₁ t ₁ u ₂ t ₂ ... u _k t _k u _{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

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

В Берляндии по воскресеньям проходит известое шоу — игра «Слабое звено».

В игре принимают участие \(n\) игроков, которые выстраиваются в круг. Каждому игроку сопоставлен рейтинг — некоторое целое число \(a_i\).

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

• В очередном раунде принимают участие все ещё не выбывшие игроки.

• Все игроки, которые по рейтингу строго слабее обоих своих соседей по кругу, объявляются слабым звеном и выбывают из игры.

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

• Игра заканчивается, если после очередного раунда осталось ровно два человека или если после очередного раунда не выбыл ни один человек.

• Иначе начинается новый раунд.

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

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

Назовем подпоследовательностью массива \(a\) непустой массив \(b\) такой, что он может быть получен из массива \(a\) удалением нескольких (возможно, никаких) элементов массива \(a\). Например, массив \([1, 3]\) является попоследовательностью массива \([1, 2, 3]\), но \([3, 1]\) не является.

Назовем подотрезком массива \(a\) непустой массив \(b\) такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива \(a\). Например, \([1, 2]\) является подотрезком массива \([1, 2, 3]\), а \([1, 3]\) не является. Несложно заметить, что у массива длины \(n\) ровно \(\frac{n(n + 1)}{2}\) подотрезков.

Назовем массив \(a\) длины \(n\) возрастающим , если для любого \(1 \leq i < n\) выполняется \(a_i < a_{i + 1}\).

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив \(a\) длины \(n\). Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\).

Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(N \times M\)\(\), заполненный буквами и замостили им бесконечную плоскость. Например, прямоугольник

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