Отель представляет собой последовательность из \(n\) зданий различной высоты, построенных вплотную друг к другу. Не так давно в Отель провели кабельное телевидение, которым все теперь с удовольствием пользуются. Но есть одна проблема: на крыше \(m\)-го здания осталась куча оборудования от спутникового телевидения, которое надо с неё спустить, и вам поручили это сделать.
Попасть с земли на крышу каждого из зданий можно только посредством переносной лестницы, длина которой не меньше, чем высота здания. А уже сверху можно свободно передвигаться между соседними крышами по постоянным лестницам.
Так как оборудование для спутникового телевидения большое и тяжёлое, то вместе с оборудованием вы можете только спускаться по лестницам. В случае, если два соседних дома имеют одинаковую высоту, то перемещаться между их крышами можно без каких либо ограничений, в том числе и с оборудованием.
Оказалось, что достать длинную лестницу не так уж и просто, поэтому необходимо найти минимальную длину лестницы, подходящей для демонтажа оборудования с крыши.
На первой строке вводится два целых числа \(n, m\) \((1 \le m \le n \le 100\,000)\) — число зданий и номер здания, на котором находится оборудование, соответственно.
Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \dots, h_n\) \((1 \le h_i \le 10^9)\) — высоты зданий.
Выведите одно целое число — минимальный размер лестницы, достаточной для демонтажа.
В данном примере вам достаточно лестницы длины \(1\), так как вы можете подняться с её помощью на крышу пятого здания, далее добраться по лестницам между крышами на третью крышу, взять оборудование, после чего сначала спуститься по лестнице между третьей и четвертой, а затем — четвертой и пятой крышами. После этого можно спуститься с крыши пятого здания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
2 2 3 2 1
|
1
|