F. Неопределенная рыба-клоун
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пак Чанек только что купил пустой аквариум и мечтал заполнить его своими любимыми рыбками — рыбой-клоуном. Рыбы-клоуны нравятся Пак Чанеку тем, что они способны менять свой пол по желанию. Поскольку его аквариум очень большой, Пак Чанек хочет купить ровно $$$k$$$ рыб-клоунов, чтобы заполнить его.

Пак Чанек отправляется в местный рыбный магазин. Магазин предоставляет $$$n$$$ рыб-клоунов, пронумерованных от $$$1$$$ до $$$n$$$, причем рыба-клоун $$$i$$$ имеет размер $$$a_i$$$. Изначально каждая рыба-клоун в магазине не имеет определенного пола, но имеет возможность быть отнесенной к двум возможным полам - женскому или мужскому.

В магазине существует процедура, которой должен следовать Пак Чанек, чтобы купить рыбу-клоуна. Владелица магазина будет последовательно показывать на каждую рыбу-клоуна от $$$1$$$ до $$$n$$$ и про каждую рыбу-клоуна спрашивать у Пака Чанека, покупать ее или нет. При этом Пак Чанек должен ответить, прежде чем хозяйка магазина перейдет к следующей рыбе-клоуну. Если Пак Чанек решает купить рыбу-клоуна, о которой его спрашивают, то он также должен немедленно объявить пол, который будет присвоен этой рыбе-клоуну. При назначении пола для спрашиваемой в данный момент рыбы-клоуна должны выполняться следующие условия:

  • Если Пак Чанек назначает ее самкой, а до этого он уже покупал рыбу-клоуна женского пола, то размер текущей рыбы должен быть ровно на $$$1$$$ больше, чем размер последней самки.
  • Если Пак Чанек считает, что это самец, и он уже покупал самца рыбы-клоуна, то размер этой рыбы должен быть ровно на $$$1$$$ меньше, чем размер последнего самца.

Пак Чанек хочет купить ровно $$$k$$$ рыб-клоунов, таких, что:

  • Имеется по крайней мере одна рыба-клоун женского пола и один рыба-клоун мужского пола.
  • Среди $$$k$$$ рыб-клоунов, которых покупает Пак Чанек, средний размер самки рыбы-клоуна равен среднему размеру самца рыбы-клоуна.

Пусть $$$l$$$ и $$$r$$$ - соответственно минимальный и максимальный индекс рыбы-клоуна, которую покупает Пак Чанек. Каково минимально возможное значение $$$r-l$$$?

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq k \leq n \leq 2\cdot10^5$$$) — количество рыб-клоунов в магазине и количество рыб-клоунов, которых должен купить Пак Чанек.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) — размер каждой рыбки-клоуна.

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

Выведите минимально возможное значение $$$r-l$$$. Если невозможно купить ровно $$$k$$$ рыб-клоунов и удовлетворить условиям задачи, выведите $$$-1$$$.

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

В первом примере Пак Чанек может сделать следующее:

  1. Не покупать рыбу-клоуна $$$1$$$.
  2. Купить рыбу-клоуна $$$2$$$ и присвоить ей статус самца.
  3. Купить рыбу-клоуна $$$3$$$ и присвоить ей статус самки.
  4. Купить рыбу-клоуна за $$$4$$$ и присвоить ей статус самца.
  5. Купить рыбу-клоуна за $$$5$$$ и присвоить ей статус самца.
  6. Не покупать рыбу-клоуна $$$6$$$.
  7. Купить рыбу-клоуна $$$7$$$ и присвоить ей статус самца.
  8. Купить рыбу-клоуна $$$8$$$ и присвоить ей статус самки.
  9. Не покупать рыбу-клоуна $$$9$$$.

Тогда получаем, что:

  • Средний размер среди $$$2$$$ самок рыб-клоунов, которых покупает Пак Чанек, составляет $$$\frac{2+3}{2} = 2.5$$$.
  • Средний размер среди $$$4$$$ самцов рыбы-клоуна, которых покупает Пак Чанек, составляет $$$\frac{4+3+2+1}{4} = 2.5$$$.
  • $$$l=2$$$, $$$r=8$$$, $$$r-l=6$$$.

Стратегий с ответом лучше не существует.