Andriana มีอาเรย์วนกลับ (cyclic array) ที่สวยงาม $a = (a_0, a_1, \dots, a_{n-1})$ ซึ่งประกอบด้วยจำนวนเต็ม $n$ จำนวน โดยที่ $0 \le a_i < 2^b$ สำหรับทุก $0 \le i < n$ แต่น่าเสียดายที่เธอทำมันหายไปแล้ว! อย่างไรก็ตาม สำหรับพวกเราแล้วนี่เป็นเรื่องที่ค่อนข้างโชคดี เพราะหากไม่มีตัวเอกที่ขี้ลืมเหล่านี้ โลกนี้คงมีโจทย์แนวสร้างข้อมูลใหม่น้อยลงกว่านี้มาก
ในขณะเดียวกัน Bob เพื่อนของ Andriana มีข้อมูลที่เป็นประโยชน์อยู่บ้าง: เขาเก็บสมุดบันทึกที่จดค่า AND ระดับบิตของช่วงที่ติดกันจากอาเรย์ของ Andriana ไว้ วันหนึ่ง 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 ต้องการทราบว่าค่าที่มากที่สุดของ $k$ คือเท่าใด ที่จะทำให้สมุดบันทึกของ Bob มีข้อมูลเพียงพอที่จะสร้างอาเรย์ดั้งเดิมอันล้ำค่าของเธอขึ้นมาใหม่ได้อย่างเดียว (uniquely reconstruct)?
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองจำนวน คือ $n$ และ $b$ โดยที่ $n$ คือความยาวของอาเรย์ที่หายไปของ Andriana และ $b$ คือพารามิเตอร์ที่กำหนดข้อจำกัด $0 \le a_i < 2^b$ บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน คือ $a_i$ — สมาชิกของอาเรย์วนกลับ
ข้อมูลส่งออก
พิมพ์จำนวนเต็มเพียงตัวเดียว — ค่าที่มากที่สุดของ $k$ ที่ทำให้อาเรย์ $a$ สามารถถูกสร้างขึ้นมาใหม่ได้อย่างเดียวจากอาเรย์ $x$ ของค่า AND ของช่วง
ข้อจำกัด
$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$