Masala B

Bir kun kelib, siz qadimiy yodgorliklar daftarchasini topasiz va ichida quyidagi qiziqarli ketma-ketlik haqida ma'lumot o‘qiysiz:

Sizda ajoyib musbat butun sonlar ketma-ketligi bor:

\(a_1, a_2, \ldots, a_n\)

Har bir \((l, r)\) oralig‘i uchun \(1 \leq l \leq r \leq n\) uning sirli og‘irligi quyidagicha hisoblanadi:

\(W(l, r) = \gcd(a_l, a_{l+1}, \ldots, a_r) \times (r-l+1)\)

Bu yerda:

• \(\gcd\) — berilgan oraliqdagi sonlarning eng katta umumiy bo‘luvchisi,
• \((r-l+1)\) — oraliq uzunligi (nechta son tanlangan).

Sizga vazifa: barcha bo‘sh bo‘lmagan oraliqlar (kesmalar) ichidan eng katta sirli og‘irlikni toping.

Ya'ni, quyidagini aniqlang:

\(\max_{1 \leq l \leq r \leq n} \left( \gcd(a_l, a_{l+1}, \ldots, a_r) \times (r - l + 1) \right)\)

Qiziqartiruvchi savol: qadimiy ketma-ketlikda eng katta sirli og‘irlik qaysi oraliqqa to‘g‘ri keladi?

Birinchi qatorda bitta butun son \(n\) — massiv uzunligi.

Ikkinchi qatorda \(n\) ta musbat butun son: \(a_1, a_2, \ldots, a_n\)

\(1 \leq n \leq 2 \times 10^5\)
\(1 \leq a_i \leq 10^{12}\)

Subtask 1 — 10 ball

\(1 \leq n \leq 200\)

Subtask 2 — 15 ball

\(1 \leq n \leq 3000\)

Subtask 3 — 15 ball

Barcha elementlar teng

Subtask 4 — 20 ball

Har bir \(a[i]\) oldingisiga karrali yoki \(a_i \mid a_{i+1}\)

Subtask 5 — 40 ball

To‘liq cheklovlar

\(1 \leq n \leq 2 \times 10^5,\;1 \leq a_i \leq 10^{12}\)

Bitta butun son chiqaring — barcha oraliqlar ichidagi maksimal sirli og‘irlik qiymati.