题目描述

给定一个长度为 $n$ 的字符串 $s$，你可以在字符串末尾添加任意数列的字符。

求：最少需要添加几个字符能使字符串 $s$ 变成一个回文串？

输入格式

第一行，一个整数 $n(1 \le n \le 4 \times 10^5)$，表示字符串长度。

第二行，一个字符串 $s$。字符串 $s$ 仅由小写英文字母构成。

输出格式

输出一个整数，表示至少需要添加几个字符能使字符串 $s$ 变成一个回文串。

样例输入

3
abb

样例输出

1

样例输入

5
ababb

样例输出

3

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$|s| \le 40$
• 对于 $60\%$ 的数据，$|s| \le 4000$
• 对于 $100\%$ 的数据，$1 \le |s| \le 4 \times 10^5$，字符串 $s$ 仅由小写英文字母构成