H. O XOR do Pico

Time limit: 5000 msMemory limit: 256 MB

Um pesquisador registra $n$ medições inteiras não negativas em sequência. Todas as medições possuem valores diferentes.

O pesquisador chama um intervalo não vazio $[l,r]$ de pico coerente quando o XOR de todos os valores do intervalo é igual ao maior valor observado no mesmo intervalo. Em outras palavras,

a_l\oplus a_{l+1}\oplus\cdots\oplus a_r=\max_{l\le i\le r}a_i,

em que $\oplus$ representa o XOR bit a bit.

Conte quantos intervalos não vazios são picos coerentes.

Input

A primeira linha contém $n$ .

A segunda linha contém $n$ inteiros $a_1,\ldots,a_n$ .

Output

Imprima um único inteiro: o número de intervalos $[l,r]$ que satisfazem a condição.

Samples

Sample 1

Input

1
7

Output

O único intervalo possui XOR e máximo iguais a 7.

Sample 2

Input

2
0 1

Output

Os dois intervalos unitários são válidos, assim como o intervalo inteiro, cujo XOR e máximo são 1.

Sample 3

Input

3
1 2 3

Output

Todo intervalo unitário é válido; outros intervalos precisam ser verificados pela definição.