Maximize Segments with Minimum Bitwise AND Sum

You are given an array a consisting of n integers. Your task is to partition the array into as many non‐empty segments as possible such that the sum of the bitwise AND of each segment is minimized.

It can be shown that the minimal possible sum is equal to the bitwise AND of all the elements in the array, i.e., \[ g = a_1 \mathbin{\&} a_2 \mathbin{\&} \cdots \mathbin{\&} a_n, \] where \(\&\) denotes the bitwise AND operation.

You should split the array into segments such that for each segment, if you compute the bitwise AND of all its numbers, then whenever the cumulative value equals \(g\), you may end the segment and start a new one. Output the maximum number of segments that can be obtained following this property.

Note: When calculating the bitwise AND over a segment, if the result equals \(g\) at some position, you can mark the end of a segment and continue with the next segment from the following element.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array.

The second line contains n space-separated integers a₁, a₂, ..., a_n.

outputFormat

Output a single integer: the maximum number of segments into which the array can be partitioned such that the sum of the bitwise ANDs of the segments is minimized.

sample

3
1 1 1

3