Bedao Mini Contest 26 - Mảng OR

View as PDF

Submit solution


Points: 0.01 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~.

Với dãy đã cho và phương pháp tìm kiếm trên, 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.

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.

Scoring

Subtask Điểm Giới hạn
1 ~20~ ~n \le 5000~
2 ~80~ Không có ràng buộc gì thêm

Sample Input 1

3
2 4 0

Sample Output 1

4

Sample Input 2

11
1 2 3 4 5 6 1 2 9 10 5

Sample Output 2

11

Notes

Trong ví dụ thứ nhất, gọi ~f(l, r)~ ~=~ ~a_l~ ~|~ ~a_{l + 1}~ ~|~ ~\cdots~ ~|~ ~a_r~. Có thể tìm kiếm các số sau: ~f(1, 1) = 2~, ~f(1, 2) = 6~, ~f(1, 3) = 6~, ~f(2, 2) = 4~, ~f(2, 3) = 4~, ~f(3, 3) = 0~.

Vậy có thể tìm kiếm tối đa ~4~ giá trị phân biệt là ~0, 2, 4, 6~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.