2168. Руны в поле @ Timus Online Judge

2168. Руны в поле

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ

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

После тщетных попыток поднять первую руну, он обошёл их все и нашёл на земле древний манускрипт. В нём было написано, что возможно поднять любое количество рун за один раз при нескольких условиях:

Все такие руны должны лежать по порядку, то есть, представив, что руны пронумерованы от 1 до N, можно поднять руны с l-й по r-ю, причём все эти руны должны быть ещё не подняты;
Какой-то нетривиальный префикс этого отрезка рун должен совпадать с суффиксом этого отрезка такой же длины. Нетривиальный — то есть, не совпадающий со всем отрезком. Например, Вадим сможет поднять поднять отрезок «abcdab», потому что есть префикс «ab», сможет поднять «aa», потому что есть префикс «a», также сможет поднять «abcabcab», потому что есть префикс «abcab», а вот «abc» или «a» поднять он не сможет никак;
Эти действия можно повторять сколько угодно раз, но возвращать руны обратно или на другое место нельзя.

Прочитав этот манускрипт, Вадим понял, что времени думать у него совсем нет, поэтому он попросил Вас помочь ему посчитать наибольшее количество рун, которое он сможет унести с собой.

Исходные данные

В первой строке дано целое число N — количество рун в поле (1 ≤ N ≤ 10⁵).

Во второй строке описаны эти руны одной строкой, состоящей из строчных латинских букв.

Результат

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

Примеры

исходные данные	результат
6 abcdab	6
7 abcdabd	6
6 abacdc	6

Автор задачи: Вадим Баринов
Источник задачи: Уральская командная олимпиада по программированию 2022