(tongchan.*)

Trên giá sách của thư viện trường THPT chuyên Phan Bội Châu có \(n\) quyển sách được đánh số thứ tự \(1,\ 2,\ldots,n\ (2 \leq n \leq 10^{6})\). Mỗi quyển sách có số lượng trang tương ứng là \(a_{1},a_{2},\ldots,a_{n}\ (a_{i} \leq 10^{4},1 \leq i \leq n)\).

Yêu cầu: Tính số lượng tất cả các cách để có thể lấy 2 quyển sách trong số \(n\) quyển sách sao cho tổng số lượng trang sách trong \(n - 2\) quyển sách còn lại trên giá là một số chẵn.

Dữ liệu vào:

+ Dòng thứ nhất chứa số nguyên dương \(n\)

+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\)

Kết quả:

+ Ghi một số nguyên duy nhất là kết quả của bài toán

Ví dụ:

Giải thích: Có 4 cách chọn là

Cách 1: lấy quyển 1 và quyển 2 thì tổng số trang sách của các quyển còn lại là: \(27 + 64 + 75 = 166\) là số chẵn

Cách 2: lấy quyển 1 và quyển 4 thì tổng số trang sách của các quyển còn lại là: \(58 + 27 + 75 = 138\) là số chẵn

Cách 3: lấy quyển 2 và quyển 4 thì tổng số trang sách của các quyển còn lại là: \(36 + 27 + 75 = 138\) là số chẵn

Cách 4: lấy quyển 3 và quyển 5 thì tổng số trang sách của các quyển còn lại là: \(36 + 58 + 64 = 158\) là số chẵn

Giới hạn:

+ Có 60% số test có \(n \leq 10^{4}\)

+ Có 40% số test còn lại có \(n \leq 10^{6}\)