# Fruit Sequences

## 题目描述

Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string $s_1s_2\ldots s_n$ of length $n$ . $1$ represents an apple and $0$ represents an orange. Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let $f(l,r)$ be the longest contiguous sequence of apples in the substring $s_{l}s_{l+1}\ldots s_{r}$ . Help Zookeeper find $\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$ , or the sum of $f$ across all substrings.

## 输入输出格式

### 输入格式

The first line contains a single integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$ . The next line contains a binary string $s$ of length $n$ $(s_i \in \{0,1\})$

### 输出格式

Print a single integer: $\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

## 说明

In the first test, there are ten substrings. The list of them (we let $[l,r]$ be the substring $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 The lengths of the longest contiguous sequence of ones in each of these ten substrings are $0,1,2,2,1,2,2,1,1,0$ respectively. Hence, the answer is $0+1+2+2+1+2+2+1+1+0 = 12$ .