Masala #YSKHGG9ZW7

Sizga n ta butun sonlardan iborat massiv berilgan. Har bir son o‘ziga xos bir “shadow” qiymatiga ega. Bu qiymatlar sonlarning ichki tuzilishi bilan bog‘liq bo‘lib, turli sonlarda turlicha bo‘ladi.

Massivdan ketma-ket elementlardan iborat bo‘lgan biror segment tanlash mumkin. Segmentning ahamiyati shundaki, uning ichidagi elementlarning shadow qiymatlari bir-biridan farq qiladi.

Sizning vazifangiz — shunday segmentlarning ichidan eng uzunining uzunligini topish.

Eslatma: Shadow sum har bir sonning raqamlar yig‘indisi bilan hisoblanadi. Segment ichidagi elementlarning shadow sum qiymatlari takrorlanmasligi kerak.

Har bir segmentdagi har qanday ikkita element a va b uchun EKUB(a,b) (ya’ni shadow sum qiymatlari orasidagi GCD) hisoblanadi va kerak bo‘lsa shart tekshiriladi. Segment faqat shadow sum takrorlanmasligi va EKUB shartiga mos kelganida hisobga olinadi.

Birinchi qatorda bitta butun son n beriladi (3 ≤ n ≤ 2·10⁵).
Ikkinchi qatorda n ta son — massiv elementlari.

Bitta son — shadow qiymatlari takrorlanmaydigan eng uzun segmentning uzunligi.