Cucumber

Interview

Time limit1sMemory limit1024 MB

Summary

Count the contiguous subarrays of a sequence whose maximum and minimum differ by an even number.

Level: Medium6 of 10
Topics: Array, Stack, Math
Solved: No attempts yet

Problem

Dino went to bed at 23:01. The agreement was to be asleep by 23:00 at the latest, so he now has to make up with his computer-minded parents if he wants them to bring a cucumber back from the market.

His father sent this text from the market: "You will get a sequence of N numbers. How many contiguous subsequences of that sequence have an even difference between the largest and smallest number? Try hard if you want us to bring you a cucumber!"

Dino grinned from ear to ear when he saw how trivial the task was.

Input

The first line contains a natural number N (1 ≤ N ≤ 100 000), the number from the problem text.

The second line contains a sequence of N natural numbers Ai (1 ≤ Ai ≤ 1 000 000 000, i = 1..N) separated by spaces.

Output

Print the number of contiguous subsequences in the first and only line.

Hint

Description of the second example: the contiguous subsequences where the difference between the largest and smallest number is even are: (4), (5), (2), (6), (3), (2, 6), (5, 2, 6), (2, 6, 3), (4, 5, 2, 6), (5, 2, 6, 3) and (4, 5, 2, 6, 3).

Examples3

Example 1
Input
```
3
3 3 3
```
Expected output
```
6
```
Example 2
Input
```
5
4 5 2 6 3
```
Expected output
```
11
```
Example 3
Input
```
9
4 3 6 8 4 3 5 1 6
```
Expected output
```
17
```