E. Горные цепи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы смотрите в окно и видите n гор, высота i-й горы равна hi.

Вы считаете, что две соседние горы i и (i + 1) входят в одну горную цепь, если |hi - hi + 1| ≤ k, где k — параметр схожести.

Определите минимально возможный параметр схожести k, чтобы все горы разбились на ровно m горных цепей.

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

В первой строке содержатся целые числа n и m (1 ≤ m ≤ n ≤ 2·105) — количество гор и необходимое количество горных цепей соответственно.

Во второй строке содержится n целых чисел h1, h2, ..., hn (1 ≤ hj ≤ 106,  j = 1, 2, ..., n) — высота j-й горы.

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

В единственной строке выведите единственное целое положительное число k — параметр схожести, при котором все горы разбиваются на ровно m горных цепей.

Если существует несколько возможных значений k, выведите минимальное значение.

Если решения не существует, выведите в качестве ответа  - 1.

Примеры
Входные данные
11 3
2 3 1 5 2 1 4 8 7 9 6
Выходные данные
3
Входные данные
5 3
3 1 5 7 6
Выходные данные
-1
Примечание

Первый тестовый пример

При k = 3 получаются следующие m = 3 горные цепи:

  • 1... 3: |2 - 3| ≤ 3, |3 - 1| ≤ 3, |1 - 5| > 3;
  • 4... 7: |5 - 2| ≤ 3, |2 - 1| ≤ 3, |1 - 4| ≤ 3, |4 - 8| > 3;
  • 8... 11: |8 - 7| ≤ 3, |7 - 9| ≤ 3, |9 - 6| ≤ 3.

При k = 2 будет уже 6 горных цепей.

Второй тестовый пример

При k = 2 получаются следующие 2 горные цепи:

  • 1... 2: |3 - 1| ≤ 2, |1 - 5| > 2;
  • 3... 5: |5 - 7| ≤ 2, |7 - 6| ≤ 2.

При k = 1 получаются 4 горные цепи.

Видно, что не существует k, при котором получаются ровно m = 3 горные цепи.