#1466. EVENSUB - Even subsequences

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

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ố 𝑎_𝑖 𝑛 phần tử đánh số từ 1 đế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 𝑛\ (1 ≤ n ≤ 10^5) ;
  • Dòng thứ hai chứa 𝑛 số nguyên 𝑎_𝑖\ (1 ≤ 𝑎_𝑖 ≤ 10^9) .

Dữ liệu ra:

  • Ghi ra 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ụ:

Dữ liệu vào:
5
4 5 2 6 3
Dữ liệu ra:
11
Dữ liệu vào:
9
4 3 6 8 4 3 5 1 6
Dữ liệu ra:
17

Giới hạn:

  • 40\% số điểm có 𝑛 ≤ 1000 ;
  • 30\% số điểm khác có 1 ≤ 𝑎_𝑖 ≤ 3 ;
  • 30\% số điểm còn lại không có ràng buộc gì thêm.