动物园管理员正在买一盒水果来喂他的宠物兔子。水果是苹果和橙子的序列,由长度为 $$$n$$$ 的二进制字符串 $$$s_1s_2\ldots s_n$$$ 表示。 $$$1$$$ 代表苹果,$$$0$$$ 代表橙子。
由于 wabbit 对吃橙子过敏,Zookeeper 希望找到最长的连续苹果序列。令 $$$f(l,r)$$$ 为子串 $$$s_{l}s_{l+1}\ldots s_{r}$$$ 中最长的连续苹果序列。
帮助 Zookeeper 找到 $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$,或所有子字符串中 $$$f$$$ 的总和。
输入
第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$。
下一行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$ $$$(s_i \in \{0,1\})$$$
输出
打印单个整数:$$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$。
示例
输入 #1
4 0110
输出 #1
12
输入 #2
7 1101001
输出 #2
30
输入 #3
12 011100011100
输出 #3
156
注意
在第一个测试中,有十个子字符串。它们的列表(我们让 $$$[l,r]$$$ 为子字符串 $$$s_l s_{l+1} \ldots s_r$$$):
- $$$[1,1]$$$: 0
- $$$[1,2]$$$: 01
- $$$[1,3]$$$: 011
- $$$[1,4]$$$: 0110
- $$$[2,2]$$$: 1
- $$$[2,3]$$$: 11
- $$$[2,4]$$$: 110
- $$$[3,3]$$$: 1
- $$$[3,4]$$$: 10
- $$$[4,4]$$$: 0
这十个子串中每一个的最长连续序列的长度分别为$$$0,1,2,2,1,2,2,1,1,0$$$。因此,答案是$$$0+1+2+2+1+2+2+1+1+0 = 12$$$。