题解

题面描述

小红有一个长度为$N$且只由字符$0、1$组成的字符串$S$，下标从$1$开始。她每次可以对一个字符执行翻转操作，即$0$变$1$或者$1$变为$0$。对于一个区间的权值定义为把整个区间变成全$0$或者全$1$的最少翻转次数。现在请你帮助小红求出所有子区间的权值之和。

问题本质分析

题目内容

小红有一个长度为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