Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится \(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 100\,000\))
Во второй строке находится число \(k\) (\(1 \leq k \leq n\)) — текущая позиция Федка в очереди
В следующей строке содержатся \(n-1\) число — перестановка множества терпеливостей людей в очереди \((0 \leq P_i \leq n)\)
Формат выходных данных
В первой строке выведите минимальное место, которое может стать у Федка после применения его плана
Во второй строке выведите максимальное место, которое может стать у Федка после применения его плана
-
Решения, работающие для \(n \leq 10\) будут набирать не менее 5 баллов
-
Решения, работающие для \(n \leq 1000\) будут набирать не менее 10 баллов
Замечание
Пояснение к первому тесту:
Алексей стоит на второй позиции. Перед ним один человек.
Если его терпеливость будет равна нулю, то он уйдет, и Федок станет первым
Если же его терпеливость равна трем, то он не уйдет, и Федок останется второй
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
0 3 3
|
1
2
|