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

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

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

Пусть дана строка $$$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$$$.