Задача: Подстрока-палиндром
Марина очень любит палиндромы. Палиндром — это строка, которая одинаково читается слева направо и справа налево, например « noon », « rotator » или « radar ».
Марина написала на доске строку s , состоящую из n строчных латинских букв s1 s2 ... sn . Подстрокой строки s называется строка s ls l + 1 ... sr для некоторых 1 ≤ l ≤ r ≤ n . Марина ищет в строке s как можно более длинную подстроку, которая является палиндромом. Например, в строке « rotateradars » такой подстрокой будет « radar ».
Вова хочет изменить написанную Мариной строку, чтобы подстрока-палиндром была как можно длиннее. Он может либо оставить строку нетронутой, либо изменить в ней ровно одну букву на другую. Например, если в строке « rotateradars » изменить шестую букву на « o », получится строка « rotatoradars », в которой максимальная подстрока-палиндром « rotator » имеет длину 7 . Подстроку-палиндром большей длины получить нельзя.
Помогите Вове определить, какую максимальную длину подстроки-палиндрома он сможет получить.
Входные данные
Первая строка входных данных содержит натуральное число n — длину строки, которую написала Марина ( 1 ≤ n ≤ 100 ).
Во второй строке входных данных содержится сама строка, состоящая из n строчных латинских букв.
Выходные данные
В выходной файл выведите одно число — максимальную длину подстроки-палиндрома, которую может получить Вова.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12
rotateradars |
7 |
Ваш ответ: