Fişierul intrare/ieşire:	rollercoaster.in, rollercoaster.out	Sursă	Junior Challenge 2021
Autor	Alexandru Petrescu, Stefan Constantin-Buliga	Adăugată de	Comisia •jc2021
Timp execuţie pe test	0.75 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

Un roller-coaster este format dintr-o submulţime R = {i₁, i₂, ..., i_k} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i₁, i₂), (i₂, i₃), ..., (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.

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.

Care este coeficientul maxim de distracţie ce poate fi obţinut şi pentru câte roller-coastere se obţine?

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.

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.

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
• i₁ < i₂ < ... < i_k

Exemplu

Explicaţie

Putem lua R = {1, 2, 4, 6, 7} sau R = {1, 2, 4, 5, 6, 7}.

Î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

Cum se trimit solutii?