A. Цоо шинэ функц

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарпусд $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ сөрөг биш бүхэл тоонуудаас бүрдсэн дараалал байдаг.

$a$ дарааллын хувьд $f(l, r)$ ($l, r$ бол бүхэл тоонууд, $1 ≤ l ≤ r ≤ n$) функцээр $l$-ээс $r$ хүртэлх дугаартай бүх элементүүдийн дарааллын битийн OR үйлдэлийг тодорхойлно. Томъёолбол: $f(l, r) = a_{l}\ |\ a_{l + 1}\ |\ ... \ |\ a_{r}$.

Поликарпус цаасан дээр бүх $l, r$-н ($1 ≤ l ≤ r ≤ n$) хувьд $f(l, r)$ функцуудын утгыг бичжээ. Ингээд эцэст нь хэдэн ялгаатай утга байгааг мэдэхийг хүссэн байна.

Өгөгдсөн $a$ дарааллын хувьд $f(l, r)$ функцын ялгаатай утгуудын тоог олж Поликарпусд тусал.

$x\ |\ y$ илэрхийлэл нь $x$ ба $y$ тоонуудын битийн OR үйлдэлийг илэрхийлнэ. Энэ үйлдэл орчин үеийн бүх програмчлалын хэлүүд дээр байдаг. Жишээлбэл: $C++$ and $Java$ хэлүүдэд "|" тэмдэгтээр тэмдэглэгддэг бол $Pascal$ хэлэнд "or" гэж тэмдэглэгдэнэ.

Оролт

Эхний мөрөнд $a$ дарааллын элементүүдийн тоо болох $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоо байна. Хоёр дахь мөрөнд $a$ дарааллын элементүүд болох зайгаар тусгаарлагдсан $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{6})$ бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь өгөгдсөн $a$ дарааллын $f(l, r)$ функцын ялгаатай утгуудын тоо юм

С++ хэлний оролт гаралтын хэлбэрт %lld буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл %I64d хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
1 2 0
Гаралт
4
Оролт
10
1 2 3 4 5 6 1 2 9 10
Гаралт
11

Тэмдэглэл

Эхний жишээнд Поликарпус цаасан дээр 6 тоо бичсэн:

  • $f(1, 1) = 1$
  • $f(1, 2) = 3$
  • $f(1, 3) = 3$
  • $f(2, 2) = 2$
  • $f(2, 3) = 2$
  • $f(3, 3) = 0$

Эдгээр дунд $4$ ширхэг ялгаатай утга байна: $0, 1, 2, 3$.

Сэтгэгдлүүдийг ачааллаж байна...