Đếm bộ ba XOR

Trong vương quốc BitLand, phép thuật XOR (đọc là "ex-or") là phép toán thần bí mà các pháp sư dùng để mã hóa thông điệp. Hôm nay, bạn được giao nhiệm vụ giải mã bí ẩn của dãy số phép thuật...

Phép XOR (ký hiệu \(\oplus\)) là phép toán thực hiện trên dạng nhị phân của các số theo quy tắc:

• \(0 \texttt{XOR} 0 = 0\)
• \(0 \texttt{XOR} 1 = 1\)
• \(1 \texttt{XOR} 0 = 1\)

• \(1 \texttt{XOR} 1 = 0\) (khác với phép OR thông thường)

  Quốc vương của vương quốc BitLand giao cho bạn nhiệm vụ sau : Cho dãy \(n\) viên đá phép thuật (mỗi viên mang giá trị \(a_i\)). Hãy đếm số bộ ba \((i, j, k)\) thỏa mãn:

• Vị trí: \(1 \leq i \leq j < k \leq n\)

• Đẳng thức phép thuật:
  $a_i \texttt{XOR} a_{i + 1} \texttt{XOR} ... \texttt{XOR} a_j = a_{j+1} \texttt{XOR} a_{j + 2} \texttt{XOR} ... \texttt{XOR} a_k $

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) --- số viên đá phép thuật.
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)) --- giá trị của lần lượt các viên đá.

Output

• Ghi ra trên một dòng là một số nguyên duy nhất là kết quả bài toán.

Example

6
3 1 5 3 2 6

5

Scoring

• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 50\)
• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 100\)
• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 1000\).
• \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 10^5\).