Even subsequences (evensub.*)

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.

Dữ liệu vào:

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

• Dòng thứ hai chứa \(n\ \)số nguyên \(a_{i}\) (\(1 \leq a_{i} \leq 10^{9}\)).

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

Ví dụ:

Input	Output
5 4 5 2 6 3	11
9 4 3 6 8 4 3 5 1 6	17

Chú ý:

• Có 40% số điểm có \(n \leq 1000\)

• Có 30% số điểm có \(1 \leq a_{i} \leq 3\)

• Có 30% số điểm còn lại không có ràng buộc gì thêm.