Fie A[1...n] un vector de 9c(n numere naturale. Considerăm operația reducere, care procedează după cum urmează: se aleg doi indici i, j din mulțimea {1, ..., n}, cu |i-j| > 0; se calculează b=A[i]A[j]+A[i]+A[j]; A[i] se înlocuiește cu b; A[j] se șterge. După o aplicare a operației reducere, vectorul A va avea n-1 componente. Se aplică operația reducere până se ajunge la un vector cu o singură componentă.
Cerinţă
Se cere să se scrie un program care să determine cea mai mică valoare posibilă care se poate obține pornind de la un vector dat A, după aplicarea operației reducere de n-1 ori.
Date de intrare
Programul citește din fișierul reducere.in. Pe prima linie se găsește numărul natural n, urmat de n numere naturale A[1], ..., A[n].
Date de ieşire
Programul scrie pe prima linie din fișierul reducere.out valoarea cerută modulo 666013. Numărul natural scris este urmat de caracterul sfârșit de linie.
Restricţii
1≤n, A[i]≤106
Exemple
reducere.in
reducere.out
Explicaţii
3 1 1 1
7
Numărul n de numere este 3. Numerele sunt A[1]=1, A[2]=1, A[3]=1. Minimul obținut din vectorul A este 7.
4 1 2 3 4
119
Numărul n de numere este 4. Numerele sunt A[i]=i. Minimul obținut din vectorul A este 119.