Andriana 原本有一個好靚嘅循環陣列 $a = (a_0, a_1, \dots, a_{n-1})$,入面有 $n$ 個整數,對於所有 $0 \le i < n$ 都滿足 $0 \le a_i < 2^b$,但好可惜佢唔見咗個陣列!不過對我哋嚟講,呢件事相當幸運,因為如果冇呢啲健忘嘅主角,世界上就會少好多重構問題。
與此同時,Andriana 嘅朋友 Bob 有一啲有用嘅資訊:佢有一本筆記簿,記錄咗 Andriana 陣列入面連續區間嘅按位與(AND)值。有一日 Bob 好悶,所以佢針對每個位置 $i$ 同埋某個固定長度 $k$($k \le n$),寫低咗呢個值: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (因為陣列係循環嘅,所以下標對 $n$ 取模)。冇人知 Bob 係咪透過合法途徑獲得呢啲 AND 值。
Andriana 想知道,令到 Bob 嘅筆記簿包含足夠資訊去唯一重構出佢珍貴嘅原始陣列嘅最大 $k$ 值係幾多?
輸入格式
輸入嘅第一行包含兩個整數 $n$ 同 $b$,其中 $n$ 係 Andriana 唔見咗嘅陣列長度,$b$ 係定義約束 $0 \le a_i < 2^b$ 嘅參數。 第二行包含 $n$ 個整數 $a_i$ —— 循環陣列嘅元素。
輸出格式
輸出一個整數 —— 可以由區間 AND 陣列 $x$ 唯一重構出陣列 $a$ 嘅最大 $k$ 值。
數據範圍
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
範例
輸入格式 1
6 3 7 3 7 7 3 7
輸出格式 1
2
說明
喺範例入面,$n = 6, b = 3$。陣列 $a = [7, 3, 7, 7, 3, 7]$ 嘅二進制表示為 $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$,每個元素使用三個二進制位。
當 $k = 2$ 時,陣列 $x$ 會係 $[3, 3, 7, 3, 3, 7]$(其中 $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$)。由陣列 $x$ 同埋 $b$ 嘅值,我哋可以唯一重構出 $a$。
當 $k = 3$ 時,陣列 $x$ 會係 $[3, 3, 3, 3, 3, 3]$,呢個結果唔能夠唯一確定 $a$(例如 $[3, 3, 7, 3, 7, 7]$ 都會得出相同嘅 $x$)。
因此,對於呢個範例,答案係 $k = 2$。