== include(page="template/taskheader" task_id="bomboane4") ==
Avem *N* coșuri cu bomboane, al *i*-lea coș conține *b[~i~]* bomboane. Coșurile sunt numerotate de la *1* la *n*. Poți aplica următoare operatie: alegi un interval [*st*, *dr*] și redistribui bomboanele
după următoarea regulă, fiecare element din șirul *b[~st~]*, *b[~st + 1~]*, ..., *b[~dr~]* este egal cu *(b[~st~] + b[~st + 1~] + ... + b[~dr~]) / (dr - st + 1)*. *POȚI EXECUTA ACEASTĂ OPERAȚIE DE CÂTE ORI VREI!*
Dorel vrea să afle care este cel mai mic șir in ordine lexicografică la care se poate ajunge după aplicarea operatiilor.
Avem *N* coșuri cu bomboane, al [*i*]-lea coș conține *b[~i~]* bomboane. Coșurile sunt numerotate de la *1* la *n*. Poți aplica următoare operație: alegi un interval [*st*, *dr*] și redistribui bomboanele după următoarea regulă:
* Fiecare element din șirul *b[~st~]*, *b[~st + 1~]*, ..., *b[~dr~]* devine egal cu *(b[~st~] + b[~st + 1~] + ... + b[~dr~]) / (dr - st + 1)* (adică fiecare element din subșir devine egal cu media elementelor din subșir).
Poți aplica această operație de oricâte ori vrei.
Dorel vrea să afle care este cel mai mic șir in ordine lexicografică la care se poate ajunge după aplicarea operațiilor.
_Notă: prin ordine lexicografică înțelegem sensul obișnuit, în care în loc de caractere avem numere raționale._
h2. Date de intrare
Fișierul de intrare bomboane4.in conține pe prima linie *N*, numărul de coșuri. Pe urmatoarea linie avem cele *N* coșuri.
Fișierul de intrare $bomboane4.in$ conține pe prima linie *N*, numărul de coșuri. Pe următoarea linie avem cele *N* coșuri.
h2. Date de ieșire
În fișierul de ieșire bomboane4.out vom avea șirul dorit de Dorel doar că fiecare element va fi scris ca o fracție ireductibiliă, fracțiile vor fi scrise pe linii separate.
În fișierul de ieșire $bomboane4.out$ vom avea șirul dorit de Dorel. Deoarece elementele vor fi numere raționale fiecare element va fi scris ca o fracție ireductibilă. Fracțiile vor fi scrise pe linii separate, fiecare linie conținînd două numere întregi separate printr-un spațiu, anume numărătorul și numitorul fracției.
h2. Restricții
* $1 ≤ *n* ≤ 100000$
* $1 ≤ *b[~i~]* ≤ 4000$
* $Pentru 20% din teste *n* ≤ 5000$
* 1 ≤ *n* ≤ 100 000
* 1 ≤ *b[~i~]* ≤ 40 000
* *b[~i~]* sunt numere întregi
* Pentru 40p *n* ≤ 6000
h2. Exemplu
table(example).
|_. bomboane4.in |_. bomboane4.out |
table(example).
|_. bomboane4.in |_. bomboane4.out |_. Explicație |
| 4
7 5 5 7
7 5 5 7
| 17 3
17 3
17 3
7 1
|
17 3
17 3
7 1
| Vom aplica operația [1 3] în urma căreia șirul devine 5.(6) 5.(6) 5.(6) 7
Acesta este șirul minim lexicografic. Numerele sînt scrise în formă de fracție
ireductibilă.
|
== include(page="template/taskfooter" task_id="bomboane4") ==
