题目描述

题目译自 Open Olympiad in Informatics 2020 Day1 T4 「Двойной палиндром / Double Palindrome」。

瓦尼亚在一家制造回文的工厂工作。工厂有一条长度为 $n$ 的字符串 $s$ 作为原料，由小写英文字母组成，瓦尼亚可以从中截取任意子串进行出售。回想一下，回文 是指从左到右和从右到左读取时相同的字符串。

普通的回文已经让人感到厌倦，没人购买，因此他决定生产双重回文。双重回文是指由两个等长的回文拼接而成的字符串。例如，字符串 aabb、aaaa 是双重回文，而 abba 和 aaaabb 则不是。

瓦尼亚想知道，从字符串 $s$ 中可以截取多少个双重回文，具体来说，有多少对 $(l, r)$ 使得子串 $s_l s_{l+1} \ldots s_r$ 是双重回文。帮助瓦尼亚找到这个重要问题的答案！

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 500000)$，表示字符串 $s$ 的长度。

第二行包含字符串 $s$，由小写英文字母组成。

输出格式

输出一个数字，即作为双重回文的子串数量。

6
abacac

6

在第一个样例中，有 $5$ 个长度为 $2$ 的子串是双重回文（ab、ba、ac、ca 和 ac），此外整个字符串（abacac）也是双重回文。

5
aaaaa

6

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。