Farmer John sta progettando di aprire una nuova università per mucche!
Ci sono $N$ mucche ($1 \le N \le 10^5$) che potrebbero frequentare questa università. Ogni mucca è disposta a pagare una retta massima di $c_i$ ($1 \le c_i \le 10^6$). Farmer John può fissare la retta che tutte le mucche devono pagare per iscriversi. Se questa retta supera il massimo che una mucca è disposta a pagare, la mucca non frequenterà l'università. Farmer John vuole guadagnare il più possibile per poter pagare ai suoi docenti uno stipendio equo. Determina quanto denaro può guadagnare e quale retta dovrebbe chiedere.
Input
La prima riga contiene $N$. La seconda riga contiene $N$ interi $c_1, c_2, \dots, c_N$, dove $c_i$ è la retta massima che la mucca $i$ è disposta a pagare.
Output
Stampa il massimo importo che Farmer John può guadagnare e la retta ottimale che dovrebbe chiedere. Se ci sono più soluzioni, stampa quella con la retta ottimale più bassa.
Nota che le grandi dimensioni degli interi coinvolti in questo problema potrebbero richiedere tipi interi a 64 bit (ad esempio, "long" in Java o "long long" in C/C++).
Esempi
Input 1
4 1 6 4 6
Output 1
12 4
Nota
Se Farmer John chiede $4$, allora $3$ mucche frequenteranno l'università, permettendogli di guadagnare $3 \cdot 4 = 12$.
Sottoproblemi
- I casi di test dal 2 al 4 soddisfano $c_i \le 1{,}000$.
- I casi di test dal 5 all'8 soddisfano $N \le 5{,}000$.
- I casi di test dal 9 al 12 non hanno vincoli aggiuntivi.
Autore del problema: Freddie Tang