Statement is not available in English language
A. Чтение в дороге
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юный программист Кеша сегодня участвует в соревнованиях по программированию. До места соревнований он добирается на трамвае, и ехать ему предстоит достаточно долго. В дороге Кеша обычно читает разные интересные статьи.

У Кеши на смартфоне открыты $$$n$$$ статей, которые он хотел бы прочитать. Будем считать их занумерованными от $$$1$$$ до $$$n$$$. Для чтения Кеша всегда выбирает самую короткую статью из ещё не прочитанных. Если есть несколько статей, требующих одинакового времени на чтение, Кеша всегда выбирает статью с меньшим номером.

По дороге Кеша прочитал все $$$n$$$ статей. Известен порядок номеров статей $$$a_1, a_2, \ldots, a_n$$$, в котором Кеша их читал.

Кеша обратил внимание, что на чтение статьи с номером $$$a_1$$$ он потратил время $$$t_{a_1} = 1$$$. Кроме того, он заметил, что для каждой пары статей с номерами $$$a_j$$$ и $$$a_{j+1}$$$ верно одно из двух: либо $$$t_{a_{j+1}} = t_{a_j}$$$, либо $$$t_{a_{j+1}} = t_{a_j} + 1$$$.

Ваша задача — определить минимально возможное и максимально возможное время, которое Кеша мог потратить на чтение всех статей.

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

В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество статей, прочитанных Кешей.

В каждой из следующих $$$n$$$ строк содержится по одному целому числу $$$a_j$$$ $$$(1 \le a_j \le n, j = 1, 2, \ldots, n)$$$ — номеру очередной статьи, которую читал Кеша.

Гарантируется, что для любых $$$i$$$ и $$$j$$$ верно, что если $$$i \not= j$$$, то и $$$a_i \not= a_j$$$.

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

Выведите два целых числа —минимально возможное время, которое Кеша мог потратить на чтение всех статей, и максимально возможное время, которое Кеша мог потратить на чтение всех статей. Разделяйте числа пробелом или переводом строки.

Обратите внимание, что ответ может превышать возможное значение $$$32$$$-битной целочисленной переменной, поэтому необходимо использовать $$$64$$$-битные целочисленные типы данных (тип $$$int64$$$ в языке $$$Pascal$$$, тип $$$long \, long$$$ в $$$C++$$$, тип $$$long$$$ в $$$Java$$$ и $$$C\#$$$).

Система оценки

В во всех трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для второй подзадачи требуется, чтобы программа верно решала первую подзадачу, для третьей подзадачи требуется, чтобы программа верно решала первую и вторую подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.

Тесты из условия не оцениваются.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 10)$$$n \le 10$$$нетполная
25 (до 50)$$$n \le 1000$$$1полная
35 (до 40)$$$n \le 10^5$$$1, 2полная

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

Поясним приведённый пример.

  • Самой первой Кеша прочёл статью $$$a_1 = 2$$$. Это означает, что
    • $$$t_2 = 1$$$;
    • $$$t_1 \gt t_2$$$ (иначе бы он первой прочитал статью $$$1$$$, а не $$$2$$$);
    • $$$t_3 \ge t_2$$$ (при равенстве Кеша всё равно сначала прочитает статью $$$2$$$);
    • $$$t_4 \ge t_2$$$.
  • Далее Кеша прочёл статью $$$a_2 = 3$$$:
    • $$$t_3 = t_2$$$ либо $$$t_3 = t_2 + 1$$$;
    • $$$t_1 \gt t_3$$$ (иначе бы он выбрал статью $$$1$$$ до $$$3$$$);
    • $$$t_4 \ge t_3$$$ (при равенстве Кеша всё равно выберет $$$3$$$).
  • После этого Кеша прочёл статью $$$a_3 = 1$$$:
    • $$$t_1 = t_3 + 1$$$ ($$$t_1 \gt t_3$$$ исходя из предыдущего пункта);
    • $$$t_4 \ge t_1$$$ (при равенстве Кеша всё равно выберет $$$1$$$).
  • Последней Кеша прочёл статью $$$a_4 = 4$$$:
    • $$$t_4 = t_1$$$ либо $$$t_4 = t_1 + 1$$$;

Минимальное время прочтения всех статей достигается при $$$t_2 = t_3 = 1$$$ и $$$t_1 = t_4 = 2$$$ — суммарно $$$2 + 1 + 1 + 2 = 6$$$.

Максимальное время прочтения всех статей достигается при $$$t_2 = 1$$$, $$$t_3 = 2$$$, $$$t_1 = 3$$$ и $$$t_4 = 4$$$— суммарно $$$3 + 1 + 2 + 4 = 10$$$.