Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: xorand.in

Rezultatų failas: xorand.out

Jei norite pateikti savo sprendimą - prisijunkite.

Xor ir And sankirta

Yra pateiktas masyvas A, kurį sudaro elementai a_1,a_2,\\ldots,a_n. Šio masyvo intervalui A[i:j]=<a_i,a_{i+1},\\ldots,a_j> (1\\leqi\\leqj\\leqN) apibrėžiamos dvi operacijos:

  • xor - visų elementų intervale xor'as;
  • and - visų elementų intervale and'as (and operacija atliekama pabičiui).

Pavyzdžiui, jei turimas masyvas yra A=[1,2,3,3], tai visų jo intervalų xor ir and atrodytų taip:

i j xor and 
1
1
1
1
2
2
2
3
3
4
 
1
2
3
4
2
3
4
3
4
4
 
1
3
0
3
2
1
2
3
0
3
 
1
0
0
0
2
2
2
3
3
3

Iš šios lentelės galima lengvai pastebėti, kad 6 vietose xor ir and funkcijų rezultatai sutapo. Jums reikės rasti būtent šį skaičių, t.y. xor ir and funkcijų sutapimų kiekį.

Pradiniai duomenys

Pirmojoje pradinių duomenų eilutėje nurodomas skaičius N (1\\leqN\\leq100000), nusakantis elementų masyve A kiekį. Sekančioje eilutėje pateikti skaičiai a_1,a_2,\\ldots,a_N (1\\leqa_i\\leq2^{31}-1) - masyvo A elementai.

Rezultatai

Pirmoje rezultatų eilutėje turi būti pateiktas skaičius I - intervalų, kurių elementų xor sutampa su and, kiekis.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
1 2 3 3
 
6