Question
Count Quadruplets 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 4, that is, quadruplets 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 quadruplets 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
2
Explanation
A quadruplet KaTeX can only parse string typed expression contributes to the answer if
KaTeX can only parse string typed expression is odd.
Valid quadruplets are:
(0, 2, 3, 4) → KaTeX can only parse string typed expression
(0, 1, 2, 4) → KaTeX can only parse string typed expression
Total valid quadruplets = 2.
5
1 2 3 4 5
Output
2
Explanation
A quadruplet KaTeX can only parse string typed expression contributes to the answer if
KaTeX can only parse string typed expression is odd.
Valid quadruplets are:
(0, 2, 3, 4) → KaTeX can only parse string typed expression
(0, 1, 2, 4) → KaTeX can only parse string typed expression
Total valid quadruplets = 2.