题目描述

小红定义一个字符串的权值为：极长“连续段”的数量。所谓极长“连续段”，指尽可能长的一段字符全部相同的连续子串。例如，"1100111" 共有 3 个连续段："11"、"00" 和 "111"，所以权值为 3。

现在小红拿到了一个 01 串，小红希望你帮她求出所有子串的权值之和。

输入描述

第一行输入一个正整数 n（1 <= n <= 200000），代表字符串的长度。

第二行输入一个长度为 n，且仅由'0'和'1'两种字符组成的字符串。

输出描述

一个正整数，代表所有子串的权值之和。

输入示例

4
1101

输出示例

17

提示信息

4 个长度为 1 的子串的权值均为 1。

长度为 2 的子串中，"11" 的权值为 1，"10" 和 "01" 的权值均为 2。

长度为 3 的子串中，"110" 的权值为 2，"101" 的权值为 3。

长度为 4 的子串 "1101" 的权值为 3。

总权值为 1 * 4 + 1 + 2 + 2 + 2 + 3 + 3 = 17。