Tinh linh XOR của Merlinius

Trong học viện phép thuật Arcana, mỗi pháp sư được trao một dãy số ma thuật \(A\) gồm \(n\) phần tử. Mỗi phần tử đại diện cho một tinh linh có năng lượng đặc biệt.

Hiệu trưởng Merlinius yêu cầu: hãy xác định số lượng đoạn con liên tiếp trong dãy \(A\) sao cho phép XOR tổng hợp tất cả các tinh linh trong đoạn đó có \textbfsố bit 1 là lẻ.

Một đoạn con liên tiếp là một dãy các phần tử liên tiếp trong mảng ban đầu.

Input

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

Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) \((1 \leq A_i \leq 10^9)\) --- là năng lượng của các tinh linh.

Output

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

Example

3
1 2 4

4