Đếm số dãy con

Cho một dãy $n$ số nguyên $A = (a_1, a_2, \dots, a_n)$. Ta định nghĩa dãy con của một dãy $A$ cho trước là một dãy thu được bằng cách xóa đi một số phần tử của dãy $A$, các phần tử còn lại vẫn giữ đúng thứ tự.

Ví dụ: Cho dãy $A = (8\ 6\ 5\ 2\ 7\ 4\ 9)$ với $N = 7$, dãy $(6\ 5\ 4\ 9)$ là 1 dãy con của $A$

Yêu cầu: Hãy cho biết có bao nhiêu dãy con của dãy thỏa mãn các phần tử có giá trị chẵn, lẻ hoặc lẻ, chẵn xen kẽ nhau?

Dữ liệu đọc vào từ file SUMARR.INP gồm:

• Dòng đầu là giá trị của số nguyên dương $n$ ($n \le 20$).
• Dòng thứ 2 chứa $n$ số nguyên $a_i$, mỗi số cách nhau một khoảng trắng ($i = 1, 2, \dots n$; $|a_i| < 10^6$).

Kết quả ghi ra file SUMARR.OUT một số nguyên duy nhất là số lượng dãy con thỏa mãn yêu cầu.

• $n \le 20$;
• $|a_i| < 10^6$.