Cerința

Se dau n numere naturale, \( a_{1},a_{2},…,a_{n}\), reprezentând valorile asociate nodurilor unui arbore. Construiţi arborele astfel încât suma valorilor L(u,v) să fie maximă, unde pentru orice două frunze u şi v, cu \(u< v\), ale arborelui, L(u,v) reprezintă suma valorilor \(a_{i}\) asociate nodurilor ce formează lanţul de la u la v.

Date de intrare

Fișierul de intrare arborel.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire arborel.out va conține pe primele n-1 linii câte două numere j şi h, reprezentând o muchie din arbore ce uneşte aceste două noduri.

Restricții și precizări

• 1 ≤ n ≤ 1.000
• 1 ≤ \(a_{i}\) ≤ 1.000
• punctajul se acordă relativ la soluţia maximală oficială

Exemplul 1:

arborel.in

5
1 2 3 4 5

arborel.out

1 2
1 3
2 4
2 5

Explicație

Pentru arborele afişat suma valorilor L(u,v) este 10+11+11=32. Această sumă nu este maximă.

Exemplul 2:

arborel.in

5
1 2 3 4 5

arborel.out

1 5
2 5
3 5
4 5

Explicație

Pentru arborele afişat suma valorilor L(u,v) este 8+9+10+10+11+12=60. Această sumă este maximă.