Fișierul intrare/ieșire	bomboane4.in, bomboane4.out	Sursă	Codeforces
Autor	autor necunoscut	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.03 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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 devine egal cu (b_st + b_{st + 1} + ... + b_dr) / (dr – st + 1).

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.

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.

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.

Restricții

• 1 ≤ n ≤ 100000
• 1 ≤ b_i ≤ 4000
• Pentru 20% din teste n ≤ 5000

Exemplu