Partes en la posición \(0\) de un arreglo de \(n\) enteros no negativos. Estando en la posición \(i\) puedes saltar hacia adelante cualquier distancia entre \(1\) y \(a_i\). Se garantiza que se puede llegar a la última posición. Encuentra la menor cantidad de saltos para hacerlo.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La segunda tiene los \(a_i\) \((0 \le a_i \le 10^5)\).

Salida

La menor cantidad de saltos para llegar a la posición \(n - 1\).

Ejemplo 1

Entrada

5
2 3 1 1 4

Salida

2

Ejemplo 2

Entrada

5
2 3 0 1 4

Salida

2