题目描述

A string is called a palindrome if it is read the same forward and backward. Palindromes are useful factors for measuring the complexity of strings like the asymmetry of the strings. The asymmetry of a string $S$ of length $n$ can be measured by its palindromic length, $\text{PL}(S)$, which is the minimum number of palindromic substrings into which $S$ can be partitioned. More precisely, $\text{PL}(S)$ is the minimum number $t$ ($1 \leq t \leq n$) such that there exist palindromic substrings $S_1, S_2, \dots, S_t$ whose concatenation $S_1S_2 \cdots S_t$ becomes $S$. To make it easier to distinguish, we denote a partition of $S$ into $S_1, S_2, \dots, S_t$ as $S_1 \mid S_2 \mid \cdots \mid S_t$.

For example, a string $S = \text{abaaaca}$ can be partitioned into two palindromic substrings as $\text{aba} \mid \text{aca}$, that is the minimum, so $\text{PL}(\text{abaaaca}) = 2$. A string $\text{acaba}$ cannot be partitioned into two palindromic substrings, but it can be partitioned into three palindromic substrings, $S = \text{aca} \mid \text{b} \mid \text{a}$ or $S = \text{a} \mid \text{c} \mid \text{aba}$, so $\text{PL}(\text{acaba}) = 3$. For $S = \text{radar}$, $\text{PL}(S) = 1$ because $S$ is a palindrome. $\text{PL}(S) = 5$ for $S = \text{abcde}$.

Given a non-empty string $S$ of English lowercase letters, write a program to output $\text{PL}(S)$.

输入格式

Your program is to read from standard input. The input starts with a line containing a positive integer $n$ ($1 \leq n \leq 100,000$), where $n$ is the number of letters of a string. The next line contains a string of $n$ English lowercase letters. Note that the string contains no space between the letters.

输出格式

Your program is to write to standard output. Print exactly one line. The line should contain a positive integer which is the palindromic length $\text{PL}(S)$ of the input string $S$.

6
abaaca

2

5
acaba

3

5
abcde

5

5
radar

1