Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится $n$ $(2 \leq n \leq 100\,000)$ людей, а сам Федок находится на $k-$ой $(1 \leq k \leq n)$ позиции в ней. И вот, чтобы занять себя в этой очереди, Федок стал обдумывать коварный план как побыстрее оплатить комплексный обед и начать есть.

В чем состоит коварный план? Федок хочет крикнуть, что открылась новая касса. Тогда, по его мнению, многие уйдут из очереди в поисках этой кассы, а он приблизится к заветной еде. Но вот в чем проблема: не все люди так нетерпеливы как наш герой. Проще говоря, у каждого человека есть свой параметр $P_i$ – терпеливость. Если человек стоит на позиции $x$ и его терпеливость равна $y$, то он уйдет искать новую кассу только в том случае, если $y < x$

Казалось бы, эта задача трудна, но и Федок не глуп. Он своим метким взором определил терпеливости всех людей, стоящих в очереди кроме него. Увы, так как людей очень много, в его голове все перепуталось, и некоторые числа поменялись местами. Таким образом наш герой получил некоторую перестановку множества терпеливости всех людей в очереди $P_1, P_2, \ldots, P_{n-1}$

Федок не знает точно, кто насколько терпелив и боится, что не сдвинется в очереди после реализации своей задумки. Поэтому он просит вас помочь ему узнать, какую минимальную и максимальную позицию от начала очереди он может занимать после того как крикнет: Свободная касса!

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

В первой строке входных данных находится число людей в очереди $n$ ($2 \leq n \leq 10^5$).

Во второй строке находится число $k$ ($1 \leq k \leq n$) – текущая позиция Федка в очереди.

В следующей строке содержатся $n-1$ число – перестановка множества терпеливостей людей в очереди $(0 \leq P_i \leq n)$.

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

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

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

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

• Решения, работающие для $n \leq 10$, будут набирать не менее 25 баллов.
• Решения, работающие для $n \leq 1000$, будут набирать не менее 50 баллов.

Подзадачи