오이

디노는 23시 1분에 잠자리에 들었다. 약속으로는 늦어도 23시까지 자기로 했으므로, 시장에서 오이를 사 오게 하려면 이제 정보 분야에 밝은 부모님께 잘 보여야 한다.

아버지가 시장에서 다음과 같은 문자를 보냈다. "N개의 숫자로 이루어진 수열을 받게 된다. 이 수열의 연속 부분수열 중에서 가장 큰 수와 가장 작은 수의 차이가 짝수인 것은 모두 몇 개인가? 오이를 사다 주길 바란다면 열심히 풀어 보렴!"

디노는 이 문제가 얼마나 간단한지 알아차리고 입이 귀에 걸리도록 웃었다.

첫 줄에 자연수 N (1 ≤ N ≤ 100 000)이 주어진다. 이는 문제 본문에 나온 수이다.

둘째 줄에는 공백으로 구분된 N개의 자연수 Ai (1 ≤ Ai ≤ 1 000 000 000, i = 1..N)가 주어진다.

첫 줄에 조건을 만족하는 연속 부분수열의 개수를 출력한다.

두 번째 예제에 대한 설명: 가장 큰 수와 가장 작은 수의 차이가 짝수인 연속 부분수열은 (4), (5), (2), (6), (3), (2, 6), (5, 2, 6), (2, 6, 3), (4, 5, 2, 6), (5, 2, 6, 3), (4, 5, 2, 6, 3)이다.