XOR Table Subsequence

A gigantic XOR table is pinned on a wall. Imagine that the rows and columns of this table are numbered from \(0\) upward (rows are numbered from bottom to top and columns from left to right) and the cell in row \(i\) and column \(j\) contains the number \(i\;\text{xor}\;j\). For example, the cell at \((i,j)\) is \(i\;\text{xor}\;j\).

You are given a sequence of non‐negative integers. A contiguous subsegment of the sequence is said to appear in the XOR table if it matches exactly a contiguous segment of numbers in the table that lies either horizontally (i.e. in some row, reading from left to right) or vertically (i.e. in some column, reading upward).

Formally, a contiguous subsegment \(S\) of length \(L\) appears in the table if there exist non‐negative integers \(i\) and \(j\) such that either:

• Horizontal: \(S[k] = i \;\text{xor}\; (j+k)\) for every \(0 \le k < L\), or
• Vertical: \(S[k] = (i+k) \;\text{xor}\; j\) for every \(0 \le k < L\).

Note that a subsegment of length 1 always appears in the table (since for any number \(a\) we can choose \(i=0\) and \(j=a\) to have \(0 \;\text{xor}\; a = a\)).

Observation: For a subsegment \(S\) of length \(L \ge 2\), consider its consecutive differences \(D[k] = S[k] \;\text{xor}\; S[k+1]\) for \(0 \le k < L-1\). If \(S\) appears as a contiguous segment in the XOR table then there exist some integers \(i,j\) such that for all \(0 \le k < L-1\): \[ D[k] = (\text{starting value} + k) \;\text{xor}\; (\text{starting value} + k+1). \] A key property is that for any nonnegative integer \(m\), \[ m \;\text{xor}\; (m+1) = 2^{r+1}-1 \quad (\text{where } r \text{ is the number of trailing ones in } m). \] Thus all such differences are odd and can only take values from the set \(\{1,3,7,15,\dots\}\) (since if \(x = 2^{k+1}-1\) then \(x+1\) is a power of two). Moreover, note that if we try to “align" the subsegment with the XOR table the differences must alternate in a fixed pattern:

• If the contiguous segment is taken from a row (or column) starting with an even index (in the segment of differences) then the difference at position \(0\) is always \(1\) and the pattern is: \(1, d, 1, d', \dots\) where the non-\(1\) values are in \(\{3,7,15,\dots\}\).
• If it is taken starting with an odd index then the pattern is: \(d, 1, d', 1, \dots\) where \(d, d' \) are in \(\{3,7,15,\dots\}\).

Your task is: Given the sequence, count how many of its contiguous subsegments appear in the XOR table.

inputFormat

The first line contains a single integer \(n\) \((1 \le n)\) representing the length of the sequence.

The second line contains \(n\) non‐negative integers, separated by spaces.

outputFormat

Output a single integer, the total number of contiguous subsegments of the sequence that appear in the XOR table.

sample

3
2 3 0

6