Migrated from Lutece 2862 投票

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一年一度的电子科技大学 osu! 玩家竞赛（UESTC osu! Player Contest, UESTCPC）开始了。这个竞赛会评比出电子科技大学 osu! 玩家最喜欢的谱面，依靠的方法就是玩家投票。

最终参与评比的谱面有 $26$ 个，用小写英文字母分别表示。现在有 $n$ 位同学参与投票，每人限投一票，投票结果用一个长度为 $n$ 且由小写英文字母组成的字符串表示。

Kanade 负责计票，她知道如果直接统计票数并公布排名是没办法让玩家们满足的，如果排名靠前的谱面得票数相差不多，玩家们就可能会质疑计票，加大自己的工作量。因为玩家并不知道有多少人参与了投票，所以 Kanade 决定只截取投票结果的一个子串（子串是指一个字符串中一个连续的非空子段），使得这个子段中票数最高的谱面得票数严格超过了这个子段长度的一半。

Kanade 想知道自己有多少种截取方法能够达到目的。

Input

第一行一个整数 $n\ (1\le n\le 10^5)$，表示总共的参与投票人数。

第二行一个长为 $n$ 且由小写字母组成的字符串，表示投票结果。

Output

输出一行一个整数，表示截取方法数。

Samples

5
ccccb

14

Resources

The 19th UESTC Programming Contest Preliminary