Cho một dãy gồm ~n~ số nguyên dương.

Yêu cầu: Xác định số cách chọn hai phần tử trong dãy số sao cho tổng hai phần tử này có giá trị chẵn.

Input

• Dòng thứ nhất ghi số nguyên dương ~n~ (~1≤n≤10^5~).

• Dòng thứ hai ghi ~n~ số nguyên dương ~a_i~ (~1≤a_i≤10^3~).

Output

• Một số là kết quả tìm được.

Examples

Input1

5
2 7 1 4 2

Output1

4

Input2

5
2 4 7 8 6

Output2

6

Note

• Giải thích ví dụ 1: Các cặp số được chọn là (2;4),(2;2),(4;2),(7;1).

• Giải thích ví dụ 2: Các cặp số được chọn là (2;4),(2;8),(2;6),(4;8),(4;6),(8;6).