== include(page="template/taskheader" task_id="rollercoaster") ==

În vacanţa de vară, Phineas şi Ferb vor să construiască un roller-coaster. În oraşul Danville se află $N$ turnuri în linie dreaptă. Cel de-al $i$-lea turn de la stânga la dreapta are înălţimea $H{~i~}$.

În vacanţa de vară, Phineas şi Ferb vor să construiască un roller-coaster. În oraşul Danville se află N turnuri în linie dreaptă. Cel de-al i-lea turn de la stânga la dreapta are înălţimea h[i].

Un roller-coaster este format dintr-o submulţime $R = {i{~1~}, i{~2~}, ..., i{~k~}}$ din cele $N$ turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri $(i{~1~}, i{~2~}), (i{~2~}, i{~3~}), ..., (i{~k-1~}, i{~k~})$

Un roller-coaster este format dintr-o submulţime R = {i{~1~}, i{~2~}, ..., i{~k~}} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i{~1~}, i{~2~}), (i{~2~}, i{~3~}), ..., (i{~k-1~}, i{~k~})

Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea $A$ de un turn cu înălţimea $B$ are coeficientul de distracţie $cmmdc(A, B)$. Coeficientul de distracţie al unui roller-coaster este egal cu suma coeficienţilor pistelor care îl alcătuiesc.

Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea h{~1~} de un turn cu înălţimea h{~2~} are coeficientul de distracţie cmmdc(h{~1~}, h{~2~}). Coeficientul de distracţie al unui roller-coaster este egal cu suma coeficienţilor pistelor care îl alcătuiesc.

Marcel a promis că îi ajută pe Phineas şi Ferb să îşi pună planul în aplicare cu speranţa de a apărea şi el într-un episod.

h2. Restricţii si precizări

* $N ≤ 250.000$
* $H{~i~} ≤ 250.000, 1 ≤ i ≤ N$
* *$Subtaskul 1 (20 de puncte):$* $N ≤ 15$
* *$Subtaskul 2 (20 de puncte):$* $N ≤ 1000$
* *$Subtaskul 3 (60 de puncte):$* restricţiile iniţiale

* N ≤ 250 000
* h[i] ≤ 250 000, 1 ≤ i ≤ N
* pentru 20% din punctaj, N ≤ 15
* pentru 40% din punctaj, N ≤ 1000

* **i{~1~} < i{~2~} < ... < i{~k~}**