D. Тоонуудын хослол

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

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

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

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

Симонд $n$ ширхэг элементтэй $a_1$, $a_2$, ..., $a_n$ цуваа байв. Өнөөдөр Симон дараах нөхцөлийг хангах $l$, $r$ ($1$ ≤ $l$ ≤ $r$ ≤ $n$) хосуудыг олж өгөхийг хүсэв.

  1. ($l≤j≤r$) нөхцлийг хангах $a_l$, $a_{l+1}$,... $a_r$-ийг бүгдийг нь хуваадаг $a_j$ байх $j$ тоо олддог байх
  2. Эхний нөхцөлийг хангадаг бүх хос ($l, r$) тоонуудын хувьд ($r-l$) нь хамгийн их утгыг авна

Симонд тусалж ($l, r$)-ийн бүх хослолыг олж өгнө үү?

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ ($1≤n≤3·10^5$) Хоёр дахь мөрөнд $n$ ширхэг тоо зайгаар тусгаарлагдан өгөгдөнө $a_1$, $a_2$, ..., $a_n$ ($1 ≤ ai ≤ 10^6$).

Гаралт

Эхний мөрөнд хоёр бүхэл тоо хэвлэ хослолуудын тоо болон хослолын хамгийн их утга $r - l$. Өсөх эрэмбээр $l$ утгуудыг хэвлэ.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: byambadorjp

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

Оролт
5
4 6 9 3 6
Гаралт
1 3
2 
Оролт
5
1 3 5 7 9
Гаралт
1 4
1 
Оролт
5
2 3 5 7 11
Гаралт
5 0
1 2 3 4 5 

Тэмдэглэл

In the first sample the pair of numbers is right, as numbers $6, 9, 3$ are divisible by $3$.

In the second sample all numbers are divisible by number $1$.

In the third sample all numbers are prime, so conditions $1$ and $2$ are true only for pairs of numbers $(1, 1)$, $(2, 2)$, $(3, 3)$, $(4, 4)$, $(5, 5)$.

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