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

Будем называть последовательность, состоящую из целых положительных чисел, корректной , если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности [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 .

Назовем подпоследовательностью массива \(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\).

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.

Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).

Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.

По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.

Вы должны выводить свой ответ по модулю \(1234567\).

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

Вам дан массив \(V\) длины \(n\), и вы хотите уметь осуществлять над ним следующие операции:

1) get(\(a\), \(b\)) - узнать наибольший общий делитель чисел на отрезке от \(a\) до \(b\).

2) update(\(a\), \(b\), \(k\)) - для всех \(j\) от \(a\) до \(b\) увеличить \(j\)-е число на \(k \cdot (j - a + 1)\), т.е.

\(V_a += k\)

\(V_{a+1} += 2 \cdot k\)

...

\(V_b += (b - a + 1) \cdot k\)