Farmer John está a planear abrir uma nova universidade para vacas!
Existem $N$ vacas ($1 \le N \le 10^5$) que poderão frequentar esta universidade. Cada vaca está disposta a pagar uma propina máxima de $c_i$ ($1 \le c_i \le 10^6$). Farmer John pode definir a propina que todas as vacas devem pagar para se inscreverem. Se esta propina for superior ao máximo que uma vaca está disposta a pagar, essa vaca não frequentará a universidade. Farmer John quer ganhar o máximo de dinheiro possível para pagar um salário justo aos seus professores. Determine quanto dinheiro pode ganhar e que propina deve cobrar.
Entrada
A primeira linha contém $N$. A segunda linha contém $N$ inteiros $c_1, c_2, \dots, c_N$, em que $c_i$ é a propina máxima que a vaca $i$ está disposta a pagar.
Saída
Imprima o montante máximo que Farmer John pode ganhar e a propina ótima que deve cobrar. Se houver várias soluções, imprima a solução com a menor propina ótima.
Note que os valores elevados dos inteiros envolvidos neste problema podem exigir tipos inteiros de 64 bits (por exemplo, "long" em Java ou "long long" em C/C++).
Exemplos
Entrada 1
4 1 6 4 6
Saída 1
12 4
Nota
Se Farmer John cobrar $4$, então $3$ vacas frequentarão a universidade, permitindo-lhe ganhar $3 \cdot 4 = 12$.
Subtarefas
- Os casos de teste 2 a 4 satisfazem $c_i \le 1{,}000$.
- Os casos de teste 5 a 8 satisfazem $N \le 5{,}000$.
- Os casos de teste 9 a 12 não têm restrições adicionais.
Autor do problema: Freddie Tang