Prieteni

Mai mulţi prieteni iubitori ai muntelui au parte de o adevărată aventură, într-una din zilele vacanţei de iarnă. Surprinşi de dificultatea traseului ales spre parcurgere şi de înrăutăţirea rapidă a condiţiilor meteo (ninsoare şi viscol) îşi dau seama, odată cu lăsarea întunericului, că ar fi mai bine să se adăpostească pe timpul nopţii, urmând să revină la cabană în dimineaţa zilei următoare. Norocul pare să le surâdă în cele din urmă. Pe partea cealaltă a prăpastiei la marginea căreia se află, se zăreşte un refugiu.. Cercetând împrejurimile, descoperă un podeţ din lemn care i-ar putea ajuta să traverseze prăpastia. După o evaluare mai atentă, realizează că traversarea nu va fi deloc uşoară, pentru că există câteva traverse lipsă, iar starea podeţului permite traversarea sa de către cel mult $2$ persoane, la un moment dat. Vizibilitatea este extrem de redusă şi mai există o singură lanternă funcţională ce va trebui folosită judicios pentru traversarea în siguranţă a tuturor membrilor grupului. Traversarea se va face alternativ în ambele sensuri, pentru a putea readuce lanterna celor care n-au traversat încă.

Cerință

Cunoscând numărul membrilor grupului, timpul fiecăruia de traversare (exprimat în secunde) şi ştiind că, la o traversare în care sunt angajaţi doi membri, timpul este dat de timpul de traversare al celui mai lent dintre ei, găsiţi o strategie adecvată pentru ca toţi membrii grupului să traverseze prăpastia în timpul cel mai scurt. Dacă există mai multe soluţii cu acelaşi timp minim de traversare, se va determina numai una, oricare dintre ele.

Date de intrare

Datele de intrare se preiau din fişierul prieteni.in. Acesta conţine pe prima linie valoarea $n$, adică numărul prietenilor, iar pe următoarele $n$ linii câte un număr pe linie, numărul $t_i$ aflat pe linia $i+1$ din fişier, reprezentând timpul (exprimat în secunde) în care persoana $i$ din grup poate traversa singură podeţul.

Date de ieșire

Soluţia se va scrie în fişierul prieteni.out. Pe primele $n$ linii se va descrie strategia urmată pentru atingerea acestui timp minim: fiecare linie $i$ va conţine una sau două valori, indicând persoana sau persoanele ce traversează podeţul la pasul $i$. Fiecare persoană este indicată chiar prin timpul său de traversare, specificat corespunzător în fişierul cu datele de intrare prieteni.in.
Pe ultima linie se va scrie valoarea ce reprezintă timpul minim total (exprimat în secunde) necesar pentru ca toţi cei $n$ membri ai grupului să traverseze prăpastia.

Restricții și precizări

• $1 \leq n \leq 1 \ 000$;
• în orice moment pot traversa podeţul cel mult $2$ membri ai grupului;
• $1 \leq t_i \leq 1 \ 000$;
• pot exista mai multe persoane cu acelaşi timp de traversare, dar în specificarea soluţiei nu are importanţă cărei persoane îi aparţine timpul respectiv.

Exemplu

prieteni.in

3
2
3
5

prieteni.out

2 3
2
2 5
10

Explicație

Mai întâi traversează persoanele $1$ şi $2$, având timpii $2$, respectiv $3$ secunde. Timpul de traversare la această trecere este dat de timpul cel mai mare: $3$ secunde. Se întoarce apoi persoana $1$ cu lanterna, timpul de traversare fiind de $2$ secunde. La a treia traversare, trec persoanele $1$ şi $3$, având timpii $2$, respectiv $5$ secunde. De data aceasta, timpul de traversare la această trecere este dat de timpul cel mai mare: $5$ secunde. Timp total: $3+2+5=10$ secunde.

Aceasta este una dintre strategiile posibile. O altă soluţie corectă: traversează mai întâi persoana $1$ cu persoana $3$, se întoarce persoana $1$ şi traversează apoi persoana $1$ cu persoana $2$, şi în acest caz se obţine acelaşi timp minim de $10$ secunde.