题解

给定一个仅包含 '0' 和 '1' 的字符串 S，我们需要计算所有子区间的权值之和。定义每个子区间的权值为将该子区间内的所有数字变为 '0' 或 '1' 所需要的最少翻转次数。对于一个子区间，记 '0' 的个数为 c0，'1' 的个数为 c1，则最少翻转次数为：

$\text{min}(c0, c1) =$$\frac{c0 + c1 - |c0 - c1|}{2}$

即：

$\frac{\text{区间长度} - |c0 - c1|}{2}$

题目内容

小红有一个长度为$N$且只由字符$0、1$组成的字符串$S$，下标从$1$开始。

她每次可以对一个字符执行翻转操作，即$0$变$1$或者把$1$变成$0$。

对于一个区间的权值为把整个区间变成全$0$或者全$1$的最少翻转次数。

现在请你帮助小红求出所有子区间的权值之和

输入描述

第一行一个整数$N(1≤N≤5×10^5)$表示字符串长度。

第二行一个长度为$N$的字符串，表示$S$。数据保证输入只含$0、1$。

输出描述

一个整数，表示所有子区间的权值之和。

样例1

输入

3
011

输出

2

样例2

输入

3
101

输出

3