Question
The Wizard’s Even-Powered Subarrays
In the kingdom of Bitland, the royal wizard loves playing with magical numbers. One day, he lined up KaTeX can only parse string typed expression magical stones, each engraved with a number.
The wizard now considers a magical sequence as any non-empty subarray of these stones. A subarray is a contiguous segment of the array.
A sequence is considered even-powered if the bitwise XOR of all its numbers is even.
Your task is to help the wizard determine how many non-empty subarrays of the given stones are even-powered.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of magical stones.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the numbers engraved on the stones.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the numbers engraved on the stones.
Output
Print a single integer — the number of non-empty subarrays whose bitwise XOR is even.
Example
Input
3
1 2 3
Output
3
Explanation
All possible non-empty subarrays are:
(1) → XOR = 1 (odd)
(2) → XOR = 2 (even)
(3) → XOR = 3 (odd)
(1, 2) → 1 ⊕ 2 = 3 (odd)
(2, 3) → 2 ⊕ 3 = 1 (odd)
(1, 2, 3) → 1 ⊕ 2 ⊕ 3 = 0 (even)
Subarrays with even XOR power are:
(2) → XOR = 2
(1, 2, 3) → XOR = 0
Total = 2 even-powered subarrays.
3
1 2 3
Output
3
Explanation
All possible non-empty subarrays are:
(1) → XOR = 1 (odd)
(2) → XOR = 2 (even)
(3) → XOR = 3 (odd)
(1, 2) → 1 ⊕ 2 = 3 (odd)
(2, 3) → 2 ⊕ 3 = 1 (odd)
(1, 2, 3) → 1 ⊕ 2 ⊕ 3 = 0 (even)
Subarrays with even XOR power are:
(2) → XOR = 2
(1, 2, 3) → XOR = 0
Total = 2 even-powered subarrays.