Description

如果一个字符串从前向后读和从后向前读相同，则称其为 回文串。回文串是用于衡量字符串复杂度（例如字符串的不对称性）的有用因子。一个长度为 $n$ 的字符串 $S$ 的不对称性可以通过其 回文长度 $\text{PL}(S)$ 来度量，即 $S$ 能被划分成的回文子串的最小数量。更精确地说，$\text{PL}(S)$ 是最小的整数 $t$ ($1 \leq t \leq n$)，使得存在回文子串 $S_1, S_2, \dots, S_t$，它们的连接 $S_1S_2 \cdots S_t$ 等于 $S$。为了便于区分，我们将 $S$ 划分为 $S_1, S_2, \dots, S_t$ 记作 $S_1 \mid S_2 \mid \cdots \mid S_t$。

例如，字符串 $S = \text{abaaca}$ 可以划分成两个回文子串，即 $\text{aba} \mid \text{aca}$，这是最小的划分，因此 $\text{PL}(\text{abaaca}) = 2$。字符串 $\text{acaba}$ 不能被划分成两个回文子串，但可以划分成三个回文子串，例如 $S = \text{aca} \mid \text{b} \mid \text{a}$ 或 $S = \text{a} \mid \text{c} \mid \text{aba}$，因此 $\text{PL}(\text{acaba}) = 3$。对于 $S = \text{radar}$，$\text{PL}(S) = 1$，因为 $S$ 本身就是一个回文串。而对于 $S = \text{abcde}$，$\text{PL}(S) = 5$。

给定一个由英文小写字母组成的非空字符串 $S$，请编写一个程序输出 $\text{PL}(S)$。

Input Format

你的程序需要从标准输入读取数据。输入的第一行包含一个正整数 $n$ ($1 \leq n \leq 100,000$)，其中 $n$ 是字符串的字母数量。接下来的一行包含一个由 $n$ 个英文小写字母组成的字符串。注意，字符串中的字母之间没有空格。

Output Format

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含一个正整数，即输入字符串 $S$ 的回文长度 $\text{PL}(S)$。

6
abaaca

2

5
acaba

3

5
abcde

5

5
radar

1

Hint

翻译由 DeepSeek V3 完成