407295: GYM102756 J Majestic Warriors of China

The Terracotta Army is a collection of terracotta sculptures depicting the armies of Qin Shi Huang, the first Emperor of China. It is a form of funerary art buried with the emperor in 210–209 BCE with the purpose of protecting the emperor in his afterlife.

Aang has been commissioned to create these fearsome warriors, and observes that the requested designs share many similarities. In fact, Aang has been able to narrow down the list of features shared by the statues to a list of only $$$K$$$ different features. For example, statues with feature #$$$1$$$ might hold a sword, statues with feature #$$$2$$$ might have a unique insignia, and so on.

Aang has even devised a concise way to describe each statue in terms of its "feature ID", a single $$$K$$$-bit integer whose binary representation tells us the set of features exhibited by the statue. As an example, suppose a statue has feature ID $$$13$$$. Since $$$13$$$ written in binary is $$$1101$$$, this means our statue exhibits features $$$1$$$, $$$3$$$, and $$$4$$$ (reading right to left), but not feature $$$2$$$. As a more general rule of thumb, we find a $$$1$$$ in the $$$2^{i-1}$$$ place if a statue exhibits feature $$$i$$$.

Always the curious fellow, Aang lined up statues $$$1 \dots N$$$ in a long row and noticed that certain ranges of statues are somewhat "majestic" in terms of the features they exhibit. A contiguous range of statues $$$i \dots j$$$ is majestic if each of the $$$K$$$ possible features is exhibited by the same number of statues in the range. Aang would like to find the largest majestic range of statues, but it is quite difficult for him to keep track of an entire army. Can you give our protagonist a hand?

The first line of input for each test case contains two integers $$$N$$$ ($$$1 \leq N \leq 100000$$$) and $$$K$$$ ($$$1 \leq K \leq 30$$$) representing the number of terracotta sculptures Aang has lined up and the number of features Aang has found, respectively. The next $$$N$$$ lines of input each contain a single integer $$$f_i$$$ ($$$0 \leq f_i \leq 2^{K}-1$$$) specifying the features present in statue $$$i$$$ using the encoding format described above.

Output a single integer representing the longest majestic range within the $$$N$$$ selected sculptures.

7 3
7
6
7
2
1
4
2

4

In the sample input, statues 3 through 6 (inclusive) form a majestic sequence of length 4.