Достигнув нужной планеты вы решили основать здесь колонию. Так как на планете множество гор, а для колонии нужна ровная поверхность, вы решили выровнять горы, используя валуны (во сне эта идея показалась вам вполне логичной).
Вам задан массив \(h_1, h_2, \dots, h_n\), в котором \(h_i\) — это высота \(i\)-й горы, и \(k\) — количество валунов в вашем распоряжении.
Вы начинаете сбрасывать валуны над первой горой по одному, и каждый валун будет двигаться следующим образом (предположим, высота текущей горы равна \(h_i\)):
- если \(h_i \ge h_{i + 1}\), валун перекатится на следующую гору;
- если \(h_i < h_{i + 1}\), валун остановится и увеличит высоту текущей горы на \(1\) (\(h_i = h_i + 1\));
- если валун достигает последней горы, то он упадет в специальную систему сбора остатков и исчезнет.
Ваша задача — определить финальную позицию \(k\)-го валуна или сказать, что он упадет в систему сбора.
Выходные данные
Для каждого набора входных данных выведите \(-1\), если \(k\)-й валун упадет в систему сбора. В противном случае выведите позицию \(k\)-го валуна.
Примечание
Промоделируем первый набор входных данных:
- Первый валун появляется в \(i = 1\); так как \(h_1 \ge h_2\), он перемещается в \(i = 2\), и остается там, так как \(h_2 < h_3\).
- Новые высоты будут равны \([4,2,2,3]\).
- Второй валун появляется в \(i = 1\); так как \(h_1 \ge h_2\), валун перемещается в \(i = 2\); так как \(h_2 \ge h_3\), валун перемещается в \(i = 3\), и остается там, как как \(h_3 < h_4\).
- Новые высоты будут равны \([4,2,3,3]\).
- Третий валун появляется в \(i = 1\); так как \(h_1 \ge h_2\), перемещается в \(i = 2\), и остается там, так как \(h_2 < h_3\).
- Новые высоты будут равны \([4,3,3,3]\).
Позиции, в которых каждый валун остановится, следующие: \([2,3,2]\).
Во втором наборе все \(7\) валунов останутся прямо на первой горе, увеличивая ее высоту от \(1\) до \(8\).
Третий набор входных данных похож на первый, но в данном случае вы сбросите \(5\) валунов. Первые три будут вести себя аналогично первому набору входных данных. После этого высоты гор станут равны \([4, 3, 3, 3]\), а потому оставшиеся два валуна упадут в систему сбора.
В четвертом наборе первый и единственный валун упадет прямо в систему сбора.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3
4 1 2 3
2 7
1 8
4 5
4 1 2 3
3 1
5 3 1
|
2
1
-1
-1
|