str

题目描述

给定一个长度为 $n$ 的 01 串 $s$，求 $s$ 中有多少个子串满足其中 1 的个数比 0 的个数多。

输入格式

第一行输入 $n$ 和 $s$。

输出格式

第一行输出一个整数 $ans$，表示答案。

输入样例#1

3 111

输出样例#1

6

说明/提示

$\texttt{Subtask}$	$n$	特殊性质	分值
$\texttt{\#1}$	$\le 3000$	无	$\texttt{20 pts}$
$\texttt{\#2}$	$\le 10 ^ 7$	$\texttt{A}$	$\texttt{10 pts}$
$\texttt{\#3}$	$\le 2 \times 10 ^ 5$	无	$\texttt{20 pts}$
$\texttt{\#4}$	$\le 2 \times 10 ^ 6$	无	$\texttt{20 pts}$
$\texttt{\#5}$	$\le 10 ^ 7$	无	$\texttt{30 pts}$

$\texttt{A:}$ $s$ 全为 1。
对于 $100\%$ 的数据，$n \le 10 ^ 7, s_i \in \{0, 1\}$。