Задача . E. Спасти Нивен!

Преодолев, наконец, Подветренные Пустоши, Ори добрался до Развалин Ветров, дабы отыскать Сердце Леса! Однако древнее хранилище, содержащее этот бесценный свет Ивы, не желало открываться!

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

Горлеки очень любили операцию «разворачивания строки». А еще они очень любили возрастающие подпоследовательности.

Пусть дана строка \(s_1s_2s_3 \ldots s_n\). Тогда «разворачиванием» этой строки назовем последовательность строк \(s_1\), \(s_1 s_2\), ..., \(s_1 s_2 \ldots s_n\), \(s_2\), \(s_2 s_3\), ..., \(s_2 s_3 \ldots s_n\), \(s_3\), \(s_3 s_4\), ..., \(s_{n-1} s_n\), \(s_n\). Например, «разворачиванием» строки 'abcd' будет последовательность строк 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.

Чтобы открыть древнее хранилище, Ори должен найти длину наибольшей возрастающей подпоследовательности «разворачивания» строки \(s\). Здесь строки сравниваются лексикографически.

Помогите Ори справиться с этой задачей!

Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:

• \(a\) — префикс \(b\), но \(a \ne b\);
• в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).