Problem B
Begin The Offensive
Miku Nakano is smitten over her tutor Fuutaro Uesugi. However, she knows competition is stiff. The other $4$ quintuplets have begun scheming elaborate plans in order to win over Fuu-kun’s heart. Despite the odds, Miku wants to remain true to herself. Miku recently has been assigned a school homework problem and being the hard worker that she is, wants to finish it without the help of Fuutaro. In Miku’s heart, that would be the true landmark of progress and she hopes to finally win Fuu-kun’s heart over!
Upon further inspection, Miku realises that the problem is harder than expected. Miku is given a sequence of $N$ numbers and needs to partition it according to the following rules:
-
Each section has the same number of elements, with only the exception of the last section having fewer if there are insufficient elements.
-
Every element in the sequence must belong to $1$ section.
-
Each section must be contiguous in the sequence.
-
Every section is pairwise disjoint with any other section except itself.
-
The bitwise AND of every number in a section must not be below $X$.
Seeing Miku struggle with this task has made you feel sad, and you want to help the best girl achieve her dream boyfriend. You need to find $k_{max}$, the maximum length of a section, or output that it is impossible.
Input
The first line contains two space-separated integers, $N$ ($1 \le N \le 250\, 000$), the length of the sequence and $X$ ($0 \leq X \leq 2^{63} - 1$), the minimum value of a section.
On the next line, there are $N$ space-separated integers, $x_{i}$ ($0 \leq x_{i} \leq 2^{63} - 1$), where $1 \leq i \leq N$, denoting the numbers of the sequence.
Output
If the sequence cannot be partitioned according to the above rules, output $-1$.
Otherwise, the output should contain a single integer, $k_{max}$, the maximum length of a section.
Explanation of Sample Input 3
-
First section has a value of $20 \, \& \, 16$ = $16 \geq 4$.
-
Second section has a value of $4 \, \& \, 4$ = $4 \geq 4$.
Therefore, the maximum length of a section is $2$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 1 1 1 1 1 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 1 1 1 1 1 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 4 20 16 4 4 |
2 |
