Even-Product Pairs

Difficulty: 1100 3500 ms 128 MB

math

Count the pairs i < j with a_i · a_j even.

Input: the first line has N; the second line has N integers.

Output: the number of even-product pairs.

Constraints:

• 2 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁹

Sample Tests

3
1 3 4

2

2
3 5

0

Read the Editorial