C. Спой, птичка!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Орнитолог Олег приехал в новый парк, чтобы насладиться пением птиц. Он слышал, что здесь обитает ровно $$$n$$$ различных птиц. Каждой из птиц он хочет поставить оценку, при этом сделать это так, чтобы все оценки были различны.

Пение каждой птицы он слушает ровно одну минуту. Если пение очередной птицы ему нравится меньше, чем какой-либо из услышанных ранее, то он ищет птицу, пение которой ему понравилось больше всего, после чего слушает её еще раз и переходит к следующей непрослушанной птице.

Гуляя по парку, Олег совсем потерял счёт времени. У него остались только оценки, которые он ставил птицам. Теперь Олег хочет узнать, сколько суммарно минут он провёл, слушая птиц. А также он хочет узнать, какое максимальное число раз он слушал одну и ту же птицу.

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

В первой строке вводится единственное натуральное число $$$n$$$ ($$$1\le n \le 200\,000$$$) — количество птиц в парке.

В следующей строке через пробел вводятся $$$n$$$ натуральных чисел $$$(1 \le a_i \le 10^9)$$$ — оценка, которую Олег поставил $$$i$$$-й птице. Обратите внимание на то, что все оценки различны.

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

Выведите через пробел два целых числа: количество минут, суммарно Олег слушал птиц, а также максимальное число раз, которое он слушал одну и ту же птицу.

Пример
Входные данные
6
2 4 1 3 5 6
Выходные данные
8 3
Примечание

В примере из условия происходило следующее:

  1. Олег послушал первую птицу и поставил ей оценку 2.
  2. Олег послушал вторую птицу и поставил ей оценку 4.
  3. Олег послушал третью птицу и поставил ей оценку 1. Так как ранее до этого он уже слышал птицу, которая понравилась ему больше, он во второй раз после этого послушал вторую птицу, у которой к тому моменту была самая высокая оценка.
  4. Олег послушал четвёртую птицу и поставил ей оценку 3. Так как ранее до этого он уже слышал птицу, которая понравилась ему больше, он во второй раз после этого послушал вторую птицу.
  5. Олег послушал пятую птицу и поставил ей оценку 5.
  6. Олег послушал шестую птицу и поставил ей оценку 6.

Таким образом Олег суммарно 8 раз слушал птиц, при этом он послушал вторую птицу 3 раза:

  • первый раз, когда подошёл к ней впервые и дал ей оценку $$$4$$$
  • второй раз после птицы с номером $$$3$$$, пение которой Олег оценил в $$$1$$$
  • третий раз после птицы с номером $$$4$$$, пение которой Олег оценил в $$$3$$$