D. Зима близко
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии зима длится n дней. Про каждый из дней известен прогноз на среднюю температуру воздуха.

У Васи есть новый комплект зимней резины, на котором можно безопасно ездить не более k дней при любой средней температуре воздуха. Через k дней использования (независимо от температуры этих дней) комплект зимней резины изнашивается. Эти k дней могут идти не подряд.

Перед первым днем зимы машина Васи всё еще на летней резине. На ней можно ездить безопасно любое количество дней, для которых средняя температура воздуха неотрицательна. Ездить на летней резине в дни, для которых средняя температура воздуха отрицательна, нельзя.

Вася может переобувать свою машину с летней резины на зимнюю и наоборот в начале любого дня.

Найдите минимальное количество раз, которое Васе нужно переобуть свою машину с летней резины на зимнюю и с зимней резины на летнюю, чтобы безопасно проездить всю зиму. По окончании зимы машина может быть на любой резине.

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

В первой строке следуют два целых положительных числа n и k (1 ≤ n ≤ 2·105, 0 ≤ k ≤ n) — количество зимних дней и количество дней, которое можно ездить на зимней резине. На зимней резине можно ездить при любой температуре, но суммарно не более k дней.

Во второй строке следует последовательность из n целых чисел t1, t2, ..., tn ( - 20 ≤ ti ≤ 20) — средняя температура воздуха в i-й день зимы.

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

Выведите минимальное количество раз, которое нужно переобуть машину с зимней резины на летнюю и с летней резины на зимнюю, чтобы безопасно проездить всю зиму. Если это невозможно, выведите -1.

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

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

Во втором примере Вася должен перед первым днем зимы поменять резину с летней на зимнюю, затем после первого дня зимы поменять резину с зимней на летнюю. После второго дня нужно вновь поменять резину с летней на зимнюю, и после третьего дня поменять резину с зимней на летнюю. Таким образом, суммарное количество смен резины равно четырем.