Tí đố An giải quyết bài toán sau: Cho một mảng gồm \(N\) số nguyên. Hãy đếm số lượng cặp chỉ số \((i, j)\) sao cho \(1 \le i < j \le N\) và tổng \(A_i + A_j\) là một số chẵn. An nhanh chóng viết một chương trình với hai vòng lặp lồng nhau duyệt qua mọi cặp \((i, j)\) để kiểm tra xem tổng có chẵn hay không. Thuật toán của An có độ phức tạp \(O(N^2)\). Khi \(N\) lên tới \(10^5\), chương trình của An cần thực hiện khoảng \(10^{10}\) phép tính và bị TLE. Bình gợi ý An chỉ cần đếm số lượng số chẵn và số lẻ trong mảng để tính kết quả nhanh hơn. Hãy giúp An lập trình thuật toán tối ưu này!

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là số lượng cặp chỉ số thỏa mãn yêu cầu.

Ví dụ

Đầu vào:

4
1 2 3 4

Đầu ra:

2

Giải thích: Các cặp chỉ số thỏa mãn là \((1, 3)\) vì \(1 + 3 = 4\) (chẵn), và \((2, 4)\) vì \(2 + 4 = 6\) (chẵn).