Farmer John планирует открыть новый университет для коров!

В этом университете потенциально могут учиться $N$ коров ($1 \le N \le 10^5$). Каждая корова готова заплатить за обучение не более $c_i$ ($1 \le c_i \le 10^6$). Farmer John может установить плату за обучение, которую должны заплатить все коровы для поступления. Если эта плата превышает максимум, который готова заплатить корова, то она не будет учиться в университете. Farmer John хочет заработать как можно больше денег, чтобы платить своим преподавателям справедливую зарплату. Определите, сколько денег он может заработать и какую плату за обучение ему следует установить.

Входные данные

Первая строка содержит $N$. Вторая строка содержит $N$ целых чисел $c_1, c_2, \dots, c_N$, где $c_i$ — максимальная плата за обучение, которую готова заплатить корова $i$.

Выходные данные

Выведите максимальную сумму, которую может заработать Farmer John, и оптимальную плату за обучение. Если существует несколько решений, выведите решение с наименьшей оптимальной платой за обучение.

Обратите внимание, что из-за большой величины целых чисел в этой задаче может потребоваться использование 64-битных целочисленных типов (например, "long" в Java или "long long" в C/C++).

Примеры

Входные данные 1

4
1 6 4 6

Выходные данные 1

12 4

Примечание

Если Farmer John установит плату $4$, то учиться будут $3$ коровы, что позволит ему заработать $3 \cdot 4 = 12$.

Подзадачи

• В тестах со 2 по 4 выполняется $c_i \le 1{,}000$.
• В тестах с 5 по 8 выполняется $N \le 5{,}000$.
• Тесты с 9 по 12 не имеют дополнительных ограничений.

Автор задачи: Freddie Tang