34751번 - 01MEX

문제

어떤 수열 $X$에 대하여 ${\text{mex}(X)}$를 $X$에 등장하지 않는 음이 아닌 정수 중 가장 작은 수로 정의하자. 예를 들어, $\text{mex} {(0, 1, 2, 3, 4)} = 5,ドル $\text{mex} {(3, 1, 0, 1)} = 2,ドル $\text{mex} {(2, 2, 1)} = 0$이다.

길이가 $N$인 수열 $A = (a_1, a_2, \cdots, a_N)$이 주어진다. 1ドル \le i \le N$인 모든 $i$에 대하여 $a_i \in \{0, 1\}$을 만족할 때, 아래 수식의 값을 구하는 프로그램을 작성해 보자.

$$\sum_{i = 1}^{N} {\sum_{j = i}^{N} {\text{mex}(a_{i}, a_{i+1}, \cdots, a_{j-1}, a_{j})}}$$

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 500,000円)$

두 번째 줄에 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. $(a_i \in \{0, 1\})$

출력

첫 번째 줄에 주어진 수식의 값을 출력한다.

제한

노트

답이 32ドル$비트 정수형의 표현 범위를 넘어갈 수 있으므로 아래와 같은 자료형을 사용하는 것을 권장한다.

• C, C++: long long
• Java: long