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$

* **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

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

* **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}.

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$

Între || apare cmmdc-ul a 2 elemente consecutive alese.
**Soluţia 1:**
- R = {1, 2, 4, 6, 7}
- 4 |1| 25 |25| 25 |5| 20 |1| 9
- 1 + 25 + 5 + 1 = 32
**Soluţia 2:**
- R = {1, 2, 4, 5, 6, 7}
- 4 |1| 25 |25| 25 |1| 28 |4| 20 |1| 9
- 1 + 25 + 1 + 4 + 1 = 32

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