Наконец лиса Кейл прибыла к своему замку!
Она должна ввести код для входа в свой замок. Консоль ввода, подключенная к её замку, немного необычна.
Консоль ввода — это прямоугольник размера 1 × n, разделенный на n одинаковых квадратных панелей. Они пронумерованы от 1 до n слева направо. Каждая панель имеет состояние ON (включено) или OFF (выключено). Изначально все панели выключены. Она может войти в её замок, тогда и только тогда, когда x1-я, x2-я, ..., xk-я панели находятся во включенном состоянии, а остальные панели находятся в выключенном состоянии.
Ей дан массив a1, a2, ..., al. За каждый ход она может выполнять следующую операцию: выбрать индекс i (1 ≤ i ≤ l), выбрать последовательные ai панелей, и изменить состояния выбранных ai панелей (т.е. ON → OFF, OFF → ON).
К сожалению, она забыла как набрать код, в условиях описанных правил. Помогите определить минимальное число операций, необходимых Кейл для того, чтобы войти в замок.
Выходные данные
Выведите наименьшее число ходов, необходимое для того, чтобы ввести код. Если это невозможно, выведите -1.
Примечание
Один из возможных способов ввести код в первом примере: на первом ходу выбрать 1-ую, 2-ую, 3-ую панели и изменить их состояния. На втором ходу можно выбрать 5-ую, 6-ую, 7-ую, 8-ую, 9-ую панели и изменить их состояния.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 8 2
1 2 3 5 6 7 8 9
3 5
|
2
|
|
2
|
3 2 1
1 2
3
|
-1
|