---
# System prepended metadata

title: ORSEQ

---

# Statement

Cho mảng $a$ có $n$ phần tử $a_1, a_2, \cdots, a_n$. Với một dãy con liên tiếp từ $l$ đến $r$, bằng cách lấy tổng OR tất cả các số, bạn tìm kiếm thêm được số mới có giá trị là $a_l$ | $a_{l + 1}$ | $\cdots$ | $a_r$. Bạn tò mò muốn biết số lượng số phân biệt tối đa có thể tìm kiếm được từ dãy đã cho.

# Input
Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^5$) --- độ dài dãy $a$.

Dòng thứ hai gồm $n$ số nguyên $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^6$) --- giá trị dãy $a$.

# Output
In ra trên một dòng là số lượng số phân biệt tối đa có thể tìm kiếm được từ dãy đã cho.

# Example
## input
```
3
1 2 0
```
## output
```
4
```

# Solution
- Nhận thấy rằng với mỗi vị trí $l$ cố định, có tối đa $logN$ vị trí $r$ mà tổng OR của đoạn thay đổi.
- Độ phức tạp: $O(NlogN)$