Đoạn XOR

Cho mảng \(A\) gồm \(n\) phần tử nguyên. Hãy đếm số lượng đoạn con liên tiếp mà tổng XOR của tất cả các phần tử trong đoạn có số bit \(1\) là lẻ.

Input

• Dòng đầu tiên là số nguyên \(n\) (\(1 \le n \le 10^6\)).

• Dòng thứ hai là \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

In ra một số nguyên là số lượng đoạn liên tiếp thỏa mãn điều kiện.

Example

Input:

3
1 2 4

Output:

4

Note

Với \(A = [1, 2, 4]\), các đoạn con liên tiếp và XOR tương ứng là:

• \([1]\): XOR \(= 1 = (1)_2\), có \(1\) bit \(1\) (lẻ) — thỏa mãn.

• \([2]\): XOR \(= 2 = (10)_2\), có \(1\) bit \(1\) (lẻ) — thỏa mãn.

• \([4]\): XOR \(= 4 = (100)_2\), có \(1\) bit \(1\) (lẻ) — thỏa mãn.

• \([1, 2]\): XOR \(= 3 = (11)_2\), có \(2\) bit \(1\) (chẵn) — không thỏa mãn.

• \([2, 4]\): XOR \(= 6 = (110)_2\), có \(2\) bit \(1\) (chẵn) — không thỏa mãn.

• \([1, 2, 4]\): XOR \(= 7 = (111)_2\), có \(3\) bit \(1\) (lẻ) — thỏa mãn.
  Vậy có \(4\) đoạn thỏa mãn, tương ứng với đáp số \(4\).