A13790 | 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)$ .