题目描述

给出一个由n个小写英文字母构成的回文串S（下标范围0<=i<n）。若从S中删掉下标i对应的字母S[i]后，得到的字符串依然是回文串，则下标i称为“优美下标”。请输出优美下标的总个数。

注意：无需真正删除字母，仅为计算答案进行假设判断。回文串是指从左往右读和从右往左读完全相同的字符串。

输入格式

第一行输入一个整数n，代表字符串S的长度。 第二行输入回文串S。

输出格式

输出一行整数，表示优美下标的总个数。

数据范围

• 80%的数据：n <= 100
• 100%的数据：n <= 1e5

样例输入

8
acaaaaca

样例输出

4

样例解释

原回文串为acaaaaca，下标3、4、5、2对应的字母均为a。删掉这4个下标中的任意一个后，得到的字符串仍为回文串，因此优美下标的个数为4。