29303번 - Чума 다국어

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

По дороге к этому городу, через каждый километр, располагаются деревни, жители которых тоже хотят уехать подальше от зараженной территории. Поэтому они собирают всех своих лошадей и в некоторый момент времени выдвигаются в сторону незараженного города. Но каждый километр пути дается им все трудней и трудней --- лошади устают, и на преодоление $i$-го километра своего пути тратят $i$ минут времени.

Доктор Хаус встретил старую женщину, которая сообщила ему, когда именно жители каждой деревни собираются начать путешествие к городу. Он понял, что, если немного заплатить, то жители некоторой деревни смогут подвезти его до какой-нибудь другой деревни на своем пути (или до незараженного города). Также сразу стало очевидно, что иногда выгодно доехать до некоторой деревни с одними жителями, а потом, немного отдохнув, присоединиться к другой группе. Отметим, что доктор Хаус может присоединиться к жителям деревни, если он сам прибыл в эту деревню не позже начала движения. Также Хаус понимал, что с его травмой ноги он не может сам пройти расстояние от одной деревни до другой.

Запутавшись в этой системе, он проснулся. Теперь его не покидает мысль, что он смог бы поспать еще, если бы нашел выход из сложившейся ситуации. Он хочет как можно быстрее добраться до незараженного города, а из всех таких возможностей, он хочет выбрать путь, который потребовал бы наименьшее количество пересадок (ему не хочется тратить деньги, так как сон только начинается).

В первой строке дано целое число $N$ ($1 \le N \le 5{\,}000$) --- число деревень на пути к городу. В следующий строке дано $N$ целых чисел $a_i$ ($1 \le a_i \le 10^6$) --- время отправления жителей из деревни $i$ в минутах (в начальный момент доктор Хаус находится в первой деревне в момент времени $1$).

В первой и единственной строке выведите два числа через пробел: минимальный момент времени, в который Хаус сможет оказаться в городе, а также количество пересадок, которые ему потребуется сделать.