思路：数学优化

暴力做法

一个最朴素的方法：枚举每个区间（$C(n,2)$个 ），计算区间中极长段的个数。 时间复杂度$O(n^2)$ ， $n = 1e5 , n^2 = 1e10 > 1e8$ , 超时。

数学优化:贡献法

考虑原串其中的某一个极长段对总体答案的贡献:

题目内容

小红最近迷上了字符串，并且认为一个字符串的美好值为字符串内，连续相同子串的数量。例如“aabbccddef”的美好值为6。

小红的朋友给了他一个01串，已经迷恋上字符串的小红想知道，这个01串所有子串的美好值之和是多少？

注：一共有$C^{2}_{n+1}$个子串

输入描述

第一行输入一个正整数$n$，代表字符串的长度。

第二行为$n$长的01串。

$1\le n\le2*10^5$

输出描述

一个整数

样例

输入

4
0011

输出

14

说明

子串分别为：0，0，1，1，00，01，11，001，011，0011

美好值分别为：1，1，1，1，1，2，1，2，2，2

总美好值为：14