Hôm nay Bờm mới được học về dãy số, Bờm thấy chúng rất thú vị, nên bài tập cô giáo cho về nhà làm Bờm đều cố gắng làm hết. Tuy nhiên đến bài cuối cùng thì Bờm nghĩ mãi không ra, và Bờm quyết định đi ngủ và đợi ngày mai hỏi các bạn thi HSG QG.

Bài toán cuối cùng của Bờm có phát biểu như sau: cho dãy số ~a_i~ có ~n~ phần tử đánh số từ ~1~ đến ~n~, đếm xem với dãy đã cho có bao nhiêu dãy con liên tiếp có chênh lệch của phần tử lớn nhất và phần tử nhỏ nhất là một số chẵn.

Hãy giúp Bờm giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

Một số nguyên duy nhất là số dãy con liên tiếp có chênh lệch giữa số lớn nhất và số nhỏ nhất là một số chẵn.

Scoring

Sample Input 1

5
4 5 2 6 3

Sample Output 1

11

Sample Input 2

9
4 3 6 8 4 3 5 1 6

Sample Output 2

17