회문 길이

어떤 문자열을 앞에서 읽든 뒤에서 읽든 같으면 회문이라고 한다. 회문은 문자열의 비대칭성처럼 복잡도를 재는 데 쓸모가 있다.

길이가 $n$인 문자열 $S$의 비대칭성은 회문 길이 $PL(S)$로 잴 수 있다. $PL(S)$는 $S$를 회문인 부분 문자열들로 나눌 때 필요한 최소 개수이다. 정확히 말하면, $PL(S)$는 $1 \le t \le n$을 만족하는 최소의 정수 $t$로, 회문인 부분 문자열 $S_1, S_2, \dots, S_t$가 존재해서 이들을 이어 붙인 $S_1 S_2 \cdots S_t$가 $S$와 같아야 한다. $S$를 $S_1, S_2, \dots, S_t$로 나눈 것은 $S_1$ | $S_2$ | $\cdots$ | $S_t$로 표기한다.

예를 들어 abaaca는 aba | aca로 두 회문으로 나눌 수 있고 이것이 최소이므로, abaaca의 경우 $PL(S) = 2$이다. acaba는 두 회문으로 나눌 수 없지만 aca | b | a나 a | c | aba처럼 세 개로 나눌 수 있으므로, acaba의 경우 $PL(S) = 3$이다. radar는 그 자체로 회문이므로 $PL(S) = 1$이다. abcde의 경우 $PL(S) = 5$이다.

첫 줄에 양의 정수 $n$ ($1 \le n \le 100\,000$)이 주어진다. $n$은 문자열의 글자 수이다. 다음 줄에는 영문 소문자 $n$개로 이루어진 문자열이 주어진다. 글자 사이에는 공백이 없다.

입력된 문자열 $S$의 회문 길이 $PL(S)$를 한 줄에 출력한다. 이 값은 양의 정수이다.