Question
Count Triplets with Odd Sum
You are given an array of KaTeX can only parse string typed expression integers. Your task is to count the number of subsequences of size 3, that is, triplets of indices KaTeX can only parse string typed expression such that KaTeX can only parse string typed expression, and the sum KaTeX can only parse string typed expression is odd.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array KaTeX can only parse string typed expression.
Output
Print a single integer — the number of triplets KaTeX can only parse string typed expression with KaTeX can only parse string typed expression such that KaTeX can only parse string typed expression is odd.
Example
Input
5
1 2 3 4 5
Output
4
Explanation
A triplet KaTeX can only parse string typed expression contributes to the answer if
KaTeX can only parse string typed expression is odd.
Valid triplets are:
(0, 1, 3) → KaTeX can only parse string typed expression
(0, 2, 4) → KaTeX can only parse string typed expression
(1, 2, 3) → KaTeX can only parse string typed expression
(1, 3, 4) → KaTeX can only parse string typed expression
Total valid triplets = 4.
5
1 2 3 4 5
Output
4
Explanation
A triplet KaTeX can only parse string typed expression contributes to the answer if
KaTeX can only parse string typed expression is odd.
Valid triplets are:
(0, 1, 3) → KaTeX can only parse string typed expression
(0, 2, 4) → KaTeX can only parse string typed expression
(1, 2, 3) → KaTeX can only parse string typed expression
(1, 3, 4) → KaTeX can only parse string typed expression
Total valid triplets = 4.