We Are Meat! We Are Gas!

Interview

Time limit2sMemory limit1024 MB

Summary

Count pairs of even-height players where the taller one stands left of the shorter one and at least one odd-height player stands between them.

Level: Medium5 of 10
Topics: Array, Segment tree
Solved: No attempts yet

Statement

The football club <> has a new coach this season. The players and the management were somewhat unhappy with the methods of the previous coach. The new coach approaches every question from a mathematical point of view. Where the old coach gathered the players in a circle before training, the new coach lines them up in alphabetical order. He is a graduate of the Institute of Precise Mathematical Education, so he can measure the height of each player to the exact centimeter.

Next, the coach has to choose the lineup for the next game. To do that, he wants to count the number of pairs of players who are "played together". Two players count as played together if, when the players are lined up in alphabetical order, the taller player stands to the left of the other, both players have even heights, and at least one player with an odd height stands between them.

The squad of Gazmyas is very large, because the club plans to move up to the Premier League. The coach cannot count the pairs by himself and asks you for help. The coach has also told you that all players have different heights.

Input

The first line contains one integer $N$ ( $1 \le N \le 10^5$ ), the number of players. The second line contains $N$ integers separated by spaces, the heights of the players. Each height is positive and does not exceed $N$ . All heights are different. The players are already in alphabetical order.

Output

Print one integer, the number of pairs of played-together players.

Examples2

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