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

Определите, за какое наименьшее число ходов фишка может попасть в самую правую клетку?

Примечание

Постарайтесь решить эту задачу, не заводя в памяти матрицу смежности.

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

Вводится число N - количество клеток (2≤N≤100). Далее вводится N натуральных чисел, записанных в клетках (каждое число не превышает 100).

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

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

Примеры

Пример ввода	Пример вывода	Пояснение
5 4 3 1 1 1	1	Из первой клетки сразу прыгаем в 5-ю.
5 2 3 1 6 1	2	Из первой клетки прыгаем в 2-ю, из 2 в 5.
5 3 3 3 3 3	2	Из первой клетки прыгаем во вторую, оттуда - в пятую. Либо из первой прыгаем в 3-ю, а оттуда - в 5-ю. Можео из первой прыгнуть в 4-ю, а оттуда - в 5-ю.