Фермер Джон має намір відкрити новий університет для корів!

Є \(N\) (\(1 \le N \le 10^5\)) корів, які потенційно можуть відвідувати університет. Кожна корова готова платити за навчання максимум \(c_i\) (\(1 \le c_i \le 10^6\)). Фермер Джон може встановити плату за навчання, яку всі корови мають сплатити. Якщо ця плата більша за ту, що корова готова платити, то вона не платить і не навчається в університеті. Фермер Джон хоче встановити таку оплату, щоб отримати максимальну суму оплат. Визначте цю максимальну суму та встановлену плату за навчання.

Формат вхідних даних

Перший рядок містить \(N\). Другий рядок містить \(N\) цілих чисел \(c_1, c_2, \dots, c_N\), де \(c_i\) – це максимальна плата, яку готова платити корова \(i\).

Формат вихідних даних

Виведіть максимальну кількість грошей, яку може отримати ФД та оптимальну оплату за навчання, яку він має встановити. Якщо є кілька варіантів, виберіть той у якому мінімальна оплата за навчання.

Зауважимо, що треба використовувати 64-бітовий цілий тип, наприклад "long" Java, або "long long" в C/C++).

Приклад вхідних даних

4
1 6 4 6

Приклад вихідних даних

12 4

ОЦІНЮВАННЯ:

• У тестах 2 - 4 \(c_i \le 1{,}000\).
• У тестах 5 - 8 \(N \le 5{,}000\).
• У тестах 9 – 12 немає додаткових обмежень.