32. Distinct Bitwise ORs of Subarrays

Difficulty: hard · Bit Manipulation, Array, Hashing

Problem

Given an array `arr` of `n` non-negative integers, compute the bitwise OR of every non-empty contiguous subarray `arr[i..j]`. Print how many **distinct** values these ORs take.

Input

- Line 1: the integer `n`. - Line 2: `n` space-separated integers.

Output

Print the number of distinct subarray OR values.

Example 1

Input:
3
1 1 2
Output:
3

Explanation: Subarray ORs: [1]=1, [1]=1, [2]=2, [1,1]=1, [1,2]=3, [1,1,2]=3. The distinct values are 1, 2 and 3.

Example 2

Input:
3
1 2 4
Output:
6

Explanation: The ORs are 1, 2, 4, 3, 6, 7, all different, so the answer is 6.

Example 3

Input:
1
0
Output:
1

Explanation: The only subarray has OR 0.

Constraints

- 1 <= n <= 10^4 - 0 <= arr[i] <= 10^9

Solutions are judged against 3 sample and 9 hidden tests. Sign in to solve it · All problems