Albo psikus!

Interview

Time limit4sMemory limit1024 MB

Summary

Count the pairs (L, R) whose contiguous segment of candy counts has an even total, for N up to 1,000,000 houses.

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

Statement

In Bajtocja there is a tradition, unknown elsewhere in the world, where at the start of autumn children dress in scary costumes and go from house to house collecting candy from residents.

Bajtek and Bitosia also plan to go out collecting candy. They live on a very long street with N houses on one side of the road, numbered 1 to N in order. They have visited this street before and know that for each i = 1, 2, ..., N, visiting house i gives exactly $C_i$ pieces of candy.

Every year they argued over the last piece of candy, so this time they are determined to collect an even number of candies. Their plan is to choose two house numbers L and R, then visit all houses between them, that is L, L+1, ..., R-1, R. This way they collect exactly $C_L + C_{L+1} + \ldots + C_{R-1} + C_R$ candies.

In how many different ways can Bajtek and Bitosia choose the houses L and R so that they collect an even number of candies?

Input

The first line contains the integer N ( $1 \le N \le 1000000$ ), the number of houses on the street. The second line contains N integers $C_1, C_2, \ldots, C_N$ ( $1 \le C_i \le 10^9$ ), where $C_i$ is the number of candies received from house i.

Output

Print one line containing the number of possible pairs of house numbers (L, R) for which the children collect an even number of candies.

Examples3

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
4
```
Example 2
Input
```
1
5
```
Expected output
```
0
```

Example 3

Input

4
1000000000 1000000000 1000000000 1000000000

Expected output