У Славика есть массив длины \(n\), состоящий только из нулей и единиц. За одну операцию он может удалить либо первый, либо последний элемент массива.
Какое минимальное число операций нужно совершить Славику, чтобы сумма оставшихся элементов в массиве равнялась в точности \(s\) после совершения всех операций? В случае, если число \(s\) не может быть получено как сумма элементов массива после любого числа операций, выведите «-1».
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество операций, необходимое чтобы сумма всех элементов массива равнялась \(s\). Выведите «-1», если получить массив с суммой элементов \(s\) невозможно.
Примечание
В первом наборе сумма элементов во всем массиве уже равна \(1\), поэтому никаких операций больше не требуется.
Во втором наборе сумма элементов равна \(2\), а нам нужна сумма \(1\), поэтому мы можем удалить из массива первый элемент, после чего массив превратится в \([1, 0]\), сумма элементов которого будет равна \(1\).
В третьем наборе сумма элементов массива изначально равна \(5\), а нам нужна сумма \(3\). Мы можем получить такую сумму удалив первые 2 элемента, после чего удалив последний элемент, сделав всего 3 операции. Массив станет \([0, 1, 1, 1, 0, 0]\), сумма элементов которого будет \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 1
1 0 0
3 1
1 1 0
9 3
0 1 0 1 1 1 0 0 1
6 4
1 1 1 1 1 1
5 1
0 0 1 1 0
16 2
1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1
6 3
1 0 1 0 0 0
|
0
1
3
2
2
7
-1
|