Se organizează o cursă automobilistică sub forma unui circuit care traversează n localităţi (numerotate in ordinea de pe circuit 1, 2, ..., n), revenind în localitatea de plecare.
Pentru oricare două localităţi învecinate se cunoaşte consumul de benzină între cele două localităţi. Mai exact, este dat un şir de n numere naturale c₁, c₂,… c_n: unde c₁ = consumul de benzină între localităţile 1 şi 2, c₂ = consumul de benzină între localităţile 2 şi 3,…, c_n = consumul de benzină între localităţile n şi 1. Cursa este coordonată de un comitet de organizare care trimite înainte de începerea cursei câte un supraveghetor în fiecare localitate. Comitetul de organizare se află într-una dintre cele n localităţi.

Cerinţă

Scrieţi un program care să determine unde trebuie stabilit sediul comitetului de organizare astfel încât consumul de benzină necesar deplasării supraveghetorilor să fie minim.

Date de intrare

Fişierul de intrare cursa.in conţine pe prima linie numărul natural n. Pe următoarele n linii se află câte un număr natural, pe linia i+1 fiind scris numărul ci (1<=i<=n).

Date de ieşire

Fişierul de ieşire cursa.out va conţine pe prima linie numărul localităţii unde se află sediul comitetului de organizare. Pe linia a doua consumul total de benzină necesar pentru deplasarea tuturor supraveghetorilor, consum obţinut însumând consumul minim de la sediu până la toate celelalte localităţi. Dacă există mai multe soluţii se va alege localitatea cu numărul minim.

Restricţii

• 2 < n < 30000
• 1 <= c_i<= 1000, pentru 1<=i<=n

Exemple

cursa.in	cursa.out	Explicatie
6 7 5 9 2 2 4	5 34	Costul total este: 6+13+11+2+0+2

prof. Nistor Eugen Mot

C. N. "N. Balcescu" Braila

emotz_ro@yahoo.co.uk