题目描述

如果一个字符串只包含一个 0 或只包含一个 1，则称这个字符串为 “孤独的串”。如 0, 1, 01, 110 都是孤独的串，而 00, 1100 都不是孤独的串。

现在给出一个长度为 N 的 01 串。问：有多少个子串是“孤独的串”？

输入格式

第一行：一个整数 $N$。

第二行：一个长度为 $N$ 的 01 字符串。

输出格式

一个整数，表示答案

输入输出 #1

样例输入

5
00111

样例输出

9

样例解释

长度为 1 的有 5 个：每个字符独自成串显然都是孤独的串

长度为 2 的有 1 个：01

长度为 3 的有 2 个：001, 011

长度为 4 的有 1 个：0111

共 9 个。

数据范围

20% 的数据：$N ≤ 50$。

50% 的数据：$N ≤ 5000$。

100% 的数据：$N ≤ 5 × 10^5$