Investigating Zeroes and Ones

Interview

Time limit0.5sMemory limit1024 MB

Summary

Count the contiguous subarrays of a binary array that contain an odd number of ones, with N up to 10^5.

Level: Easy3 of 10
Topics: Prefix sum, Math
Solved: No attempts yet

Problem

You are in a mysterious binary world where an array of $N$ binary digits is waiting for you. Each digit is either 0 or 1, and together they form a distinct pattern. Your task is to count the subarrays that contain an odd number of ones.

The array is $b_1, b_2, \ldots, b_N$ . A subarray is a segment of consecutive elements. For example, the subarrays of $[b_1, b_2, b_3]$ are $[b_1]$ , $[b_2]$ , $[b_3]$ , $[b_1, b_2]$ , $[b_2, b_3]$ , and $[b_1, b_2, b_3]$ . Count the subarrays that contain an odd number of ones. The answer may not fit in a 32-bit integer.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ), the length of the binary sequence.

The second line contains $N$ binary digits $b_1, b_2, \ldots, b_N$ ( $b_i \in \{0, 1\}$ ).

Output

Print a single line containing the number of subarrays that have an odd number of ones.

Examples2

Example 1
Input
```
3
0 1 0
```
Expected output
```
4
```
Example 2
Input
```
10
1 0 0 1 1 0 1 1 1 0
```
Expected output
```
30
```