Road Crossing

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are taking the ZNO exams next year. Prepare the sleigh in summer and the cart in winter. Therefore, they want to start preparing as soon as possible. To make the preparation more interesting, they decided to invite their classmates to join. Their classmates are in no rush to prepare for ZNO, and instead are preparing for informatics olympiads on Algotester.

Zenyk and Marichka have to visit each classmate and convince them that they need to prepare for ZNO, pass it well, enter a university, and only then can they prepare for student olympiads. Fortunately, they don’t have to walk all over the city, because all the classmates live on the same street. On one side of the street all houses have even numbers, and on the other — odd.

A total of \(n\) classmates need to be visited. Zenyk and Marichka will visit them in the order they are listed in the class student list. The \(i\)-th classmate in the list lives in the house with number \(a_i\).

Zenyk and Marichka invite you to join the preparation as well. First, solve a simple problem — count how many times they will have to cross the road.

Input

The first line gives a single integer \(n\) — the number of classmates to visit.

The second line gives \(n\) integers \(a_i\) — the numbers of the houses where the classmates live.

Output

In a single line, output a single integer — the answer to the problem.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_{i} \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 44 7 47 74 47 74	4

Notes

First Zenyk and Marichka will visit the classmates living in houses numbered 4 and 44. Then they will cross the road and visit classmates in houses 7 and 47. They will cross the road again and visit house 74. They will cross the road for the third time and visit house 47. And finally, they will cross the road to visit the last classmate who lives in the house with number 74.