Алиса и Боб любят играть в одномерный морской бой. Они играют на поле, имеющем вид строки из n квадратных клеточек (то есть на таблице 1 × n).
В начале игры Алиса в тайне от Боба расставляет на поле k кораблей, каждый из которых имеет вид прямоугольника 1 × a (то есть занимает последовательность из a подряд идущих клеток поля). Корабли не могут пересекаться и даже касаться друг друга.
После этого Боб делает последовательность «выстрелов». Он называет клетки поля, а Алиса сообщает, что клетка пуста («мимо»), либо что эта клетка принадлежит какому-либо кораблю («попал»).
Вот незадача! Похоже, Алиса любит фантазировать. Видимо, именно по этой причине на каждый ход Боба она отвечает «мимо».
Помогите Бобу уличить Алису в фантазировании — найдите первый такой ход Боба, после которого можно наверняка утверждать, что Алиса слукавила.
Выходные данные
Выведите единственное целое число — номер такого первого хода Боба, после которого можно наверняка утверждать, что Алиса сказала неправду. Ходы Боба нумеруются от 1 до m в порядке их совершения. Если искомого хода не существует, то выведите «-1».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11 3 3
5
4 8 6 1 11
|
3
|
|
2
|
5 1 3
2
1 5
|
-1
|
|
3
|
5 1 3
1
3
|
1
|