[R69E]协调串 - 代码源竞赛平台

时空限制

0.6S/512M

题目描述

我们称一个字符串是协调的，当且仅当它的第一个字符与最后一个字符相同。特别地，长度为 $1$ 的字符串也是协调的。

对于一个字符串 $u$，定义函数 $f(u)$ 表示：从 $u$ 中删除若干个字符后，使得剩余字符按原相对顺序拼接成一个协调字符串，所需删除字符数的最小值。

现在给定一个仅由小写字母组成的字符串 $s$，长度为 $n$。对于每一对满足 $1 \le l \le r \le n$ 的下标，记 $s[l..r]$ 为 $s$ 从第 $l$ 个字符到第 $r$ 个字符组成的连续子串。

你的任务是求出所有连续子串的 $f$ 值之和，即：

$$\sum_{1 \le l \le r \le n} f(s[l..r])$$

格式

输入格式

第一行包含一个整数 $n$，表示字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 且仅由小写字母组成的字符串 $s$。

输出格式

输出一行一个整数，表示所有连续子串 $s[l..r]$ 的 $f(s[l..r])$ 之和。

样例

样例输入 #1

4
abac

样例输出 #1

6

样例输入 #2

4
aaaa

样例输出 #2

0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$100$
$2$	$30$	$1000$
$3$	$40$	$10^4$

对于 $100\%$ 的数据，满足 $1 \le n \le 10^4$，且字符串 $s$ 仅包含小写字母。