== 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 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.

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.

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. Date de intrare

În fişierul de intrare rollercoaster.in se află N, numărul de turnuri, iar pe linia a doua se află cele N numere naturale nenule.

În fişierul de intrare rollercoaster.in se află $N$, numărul de turnuri, iar pe linia a doua se află cele $N$ numere naturale nenule.

h2. Date de ieşire

În fişierul de ieşire rollercoaster.out se vor afla 2 numere, reprezentând coeficientul maxim de distracţie ce poate fi obţinut de Marcel, precum şi numărul de roller-coastere prin care se obţine.

În fişierul de ieşire rollercoaster.out se vor afla $2$ numere, reprezentând coeficientul maxim de distracţie ce poate fi obţinut de Marcel, precum şi numărul de roller-coastere prin care se obţine **modulo $1.000.000.007$**.

h2. Restricţii si precizări

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

* $N ≤ 250.000$
* $H{~i~} ≤ 250.000, 1 ≤ i ≤ N$
* **i{~1~} < i{~2~} < ... < i{~k~}**
* $cmmdc(A, B)$ este cel mai mare divizor comun al lui $A$ si $B$
* *$Subtaskul 1 (20 de puncte):$* $N ≤ 15$
* *$Subtaskul 2 (20 de puncte):$* $N ≤ 1000$
* *$Subtaskul 3 (60 de puncte):$* restricţiile iniţiale
* **Numarul de roller-coastere trebuie afisat modulo 1.000.000.007**

h2. Exemplu

h3. Explicaţie

Putem lua R = {1, 2, 4, 6, 7} sau R = {1, 2, 4, 5, 6, 7}
 4 25 25 20 9
 1  25 5  1
4 25 25 28 20 9
 1  25 1  4  1

Putem lua $R = {1, 2, 4, 6, 7}$ sau $R = {1, 2, 4, 5, 6, 7}$.
 
*Soluţia 1:*
Daca alegem $R = {1, 2, 4, 6, 7}$ coeficientul de distractie total va fi:
$cmmdc(H{~1~}, H{~2~}) + cmmdc(H{~2~}, H{~4~}) + cmmdc(H{~4~}, H{~6~}) + cmmdc(H{~6~}, H{~7~}) = 1 + 25 + 5 + 1 = 32$
 
*Soluţia 2:*
Daca alegem $R = {1, 2, 4, 5, 6, 7}$ coeficientul de distractie total va fi:
$cmmdc(H{~1~}, H{~2~}) + cmmdc(H{~2~}, H{~4~}) + cmmdc(H{~4~}, H{~5~}) + cmmdc(H{~5~}, H{~6~}) + cmmdc(H{~6~}, H{~7~}) = 1 + 25 + 1 + 4 + 1 = 32$

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