站外题

给定一个长度为n 的01 串，他想知道有多少个子串，满足其中1 的个数比0 的个数多。

【输入格式】 从文件sequence.in 中读入数据。

第一行一个整数，表示字符串的长度。

第二行一个字符串，表示01 串。

【输出格式】

输出到文件sequence.out 中。

输出一行，包括一个整数，表示满足条件的子串的个数。 【数据范围】

对于20%的数据，n≤3000。

对于另外的10%的数据，n≤1e7，字符串全为1。

对于另外的20%的数据，n≤2×1e5。

对于另外的20%的数据，n≤2×1e6。

对于100%的数据，n≤1e7。