题目描述

冬天来了，你决定该给自己准备一条围巾了。

你有一块条纹布料，第 $i$ 条条纹的颜色为 $s_i$。为了方便，颜色用小写英文字母表示。

如果一个条纹序列中恰好出现两种不同的颜色，那么这个序列称为和谐的，可以用来做围巾。例如：

• ad、bcbbc 是和谐的；
• d、aaa、acb 不是和谐的。

一条围巾可能不够用，所以你对有用的布料片段感兴趣。一个非空连续片段称为有用的，当且仅当它可以被划分成若干个连续序列，并且每个连续序列都是和谐的。

例如：

• ab 是有用的；
• cbcac 是有用的，因为它可以划分为 cbc 和 ac。

请计算从整块布料中切出一个连续有用片段的方案数。

输入格式

第一行输入一个整数 $n$，表示布料中条纹数量。

第二行输入一个长度为 $n$ 的字符串 $s$，表示条纹颜色序列。

输出格式

输出一个整数，表示有用连续片段的数量。

数据范围

对于所有测试数据：

字符串 $s$ 只包含小写英文字母。

样例 1

输入

4
baba

输出

6

样例 2

输入

4
cbca

输出

5

样例解释

第一个样例中，有用片段为：ba、ba、ab、bab、aba、baba。注意，不同的片段即使作为字符串相同，只要位置不同，也要分别计数。

第二个样例中，有用片段为：cb、cbc、bc、ca、cbca。

评分方式

测试点分为 5 组。只有通过某一组的全部测试，并通过该组依赖的必要组，才能获得该组分数。