该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

“谨向英勇的中国致敬”

埃德加·斯诺到达陕甘宁边区后，决定出个NOIP(NOI Professional)题,向西方世界介绍他所看到的事情。

斯诺在调查中发现,Mao Zedong先生非常喜欢序列和区间，于是斯诺给了Mao Zedong先生一个长度为 $n$ 的，每个元素都是 $0,1,2$ 的序列。

Mao Zedong发现这个序列中一共有 $n(n+1)\over 2$ 个区间，这太多了。

运用辩证法，他认为，对于一个区间，只有其中任意一种数字的数目都不超过区间的一半时，这个区间才算是革命的。

现在Mao Zedong先生建议斯诺数一数这个序列里有多少个革命的区间。

例如，对于序列 010102201，区间201是合法的，里面每种数字只占三分之一。区间2是不革命的，2占据了这个区间的$100\%$。(由此可以看出,长度为 $1$ 的区间一定不合法)。区间0101和10是合法的，$0$ 和 $1$ 各占据了区间的一半，但是没有超过一半。

输入格式

第一行一个整数 $n$ ，表示区间的长度。

第二行一个长度为 $n$ 的只包含 $0,1,2$ 的字符串，表示给出的序列。

输出格式

一行一个整数，表示革命的区间的数量

样例数据

见下发文件中的ex1.in ~ ex5.in和ex1.ans ~ ex5.ans

数据范围

第 $1$ 个测试点，$n=100$

第 $2,3$ 个测试点，$n=1000$

第 $4$ 个测试点，$n=50000$

第 $5,6$个测试点，$n=10^5$

第 $7,8,9,10$ 个测试点，$n=5\times 10^6$

第 $2,4,5,7$ 个测试点还满足：给出的序列中只含 $0$ 和 $1$

时间限制 1s

空间限制 512MB

下发文件

下载