Юный программист Кеша сегодня участвует в соревнованиях по программированию. До места соревнований он добирается на трамвае, и ехать ему предстоит достаточно долго. В дороге Кеша обычно читает разные интересные статьи.
У Кеши на смартфоне открыты $$$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\#$$$).
В во всех трех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для второй подзадачи требуется, чтобы программа верно решала первую подзадачу, для третьей подзадачи требуется, чтобы программа верно решала первую и вторую подзадачи. Более подробно разбиение на подзадачи показано в таблице ниже.
Тесты из условия не оцениваются.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 1 (до 10) | $$$n \le 10$$$ | нет | полная |
| 2 | 5 (до 50) | $$$n \le 1000$$$ | 1 | полная |
| 3 | 5 (до 40) | $$$n \le 10^5$$$ | 1, 2 | полная |
42314
6 10
Поясним приведённый пример.
Минимальное время прочтения всех статей достигается при $$$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$$$.