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

В рамках данной задачи будет считать, что поисковик работает с базой данных, которая может быть представлена как строка s длины n. Система разрешается пользователям делать произвольные текстовые запросы к базе данных, в качестве ответа на эти запросы будет выведен список всех вхождений запроса в базу. Вхождение в базу называется появление текста-запроса в качестве подстроки строки s.

Алисе скучно, поэтому она развлекает себя тем, что открывает поисковик и вводит туда различные запросы. Изначально перед Алисой пустое текстовое поле. Каждый раз она изменяет предыдущий запрос ровно на одну букву, дописывая её в начало или в конец запроса по своему усмотрению. Алиса проделывает такую операцию ровно n раз.

В этом процессе Алисе нравится смотреть как на экране появляются все вхождения и как сильно может изменить их количество после добавления одного символа. Алиса хочет протестировать как поведёт себя поисковик если ему потребуется выводить очень много данных, поэтому она хочет выбрать такую последовательность приписываний букв в начало или конец строки, что суммарное количество вхождений всех строк-запросов в строку базы данных s будет максимально. Какое максимальное значение может получить Алиса?