Given an array $A$ consisting of $n$ integers. Count the number of contiguous subarrays such that the XOR sum of all elements in the subarray has an odd number of set bits.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print an integer, the number of contiguous subarrays satisfying the condition.
### Constraints
- $1 \leq n \leq 10^6$.
- $1 \leq A_i \leq 10^9$.
### Example
Input:
```
3
1 2 4
```
Output:
```
4
```