B. Тууз хайчилах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Скүйррел Лисс дараалалийг сонирходог. Тэрэнд бас бүхэл тоонуудын сонголт байна. Тэр бодохдоо $n$ ширхэг бүхэл тоонууд болох $a_1, a_2, ...,a_n$ нь сайн тоонууд гэе.

Тэр одоо сайн дарааллуудыг сонирхожээ. $x_1, x_2, ..., x_k$ дараалал нь сайн дараалал болох нөхцөл нь:

  • Дараалал нь эср өсөх дараалал байна, өөрөөр хэлбэл $i$ ($1 ≤ i ≤ k - 1$) бүрийн хувьд $x_i < x_{i+1}$ байна.
  • Дарааллын хөрш хоёр тоо бүр нь харилцан анхны тоо биш байна. өөрөөр хэлбэл $i$ ($1 ≤ i ≤ k - 1$) бүр нь $gcd(x_i, x_{i+1})$ байна.($gcd(p,q)$ гэдэг нь $p$ ба $q$ хоёр тоог зэрэг хуваах хамгийн их тоог хэлнэ.)
  • Дарааллын бүх элемэнтүүд нь сайн тоо байх ёстой.

Хамгийн урт дарааллыг ол.

Оролт

Эхний мөрөнд $n\ (1 ≤ n ≤ 10^5)$ сайн тоонуудын тоо өгөгдөнө. Дараагын мөрөнд $a1, a2, ..., an$ $n$ ширхэг бүхэл тооноос бүрдэх сайн тоон дараалал өгөгдөнө. (1 ≤ ai ≤ 105; ai < ai + 1).

Гаралт

Сайн дарааллын боломжит хамгийн их уртийг илэрхийлэх тоог ол.

Орчуулсан: Баярхүү

Жишээ тэстүүд

Оролт
5
2 3 4 6 9
Гаралт
4
Оролт
9
1 2 3 5 6 7 8 9 10
Гаралт
4

Тэмдэглэл

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

Сэтгэгдлүүдийг ачааллаж байна...