Uolevi has bough a new board game: Ladders. The board has $n$ squares numbered $1,2,\dots,n$. Number $a_i$ is written on square $i$. Each of the numbers $1,2,\dots,n$ occurs exactly once in $a$. For each pair of squares $(i, j)$, there is a ladder starting from $i$ and ending in $j$ if $a_j$ is a multiple of $a_i$.

When playing the game, a player can either move up one square or use one of the ladders that starts from the current square. All players start from square $1$ and their goal is to reach square $n$. Uolevi wants to calculate the minimum number of moves needed to finish the game so that he can beat Maija every time they play.

Input

The first line contain a single integers $n$. The second line contains $n$ integers $a_1,\,a_2,\dots,\,a_n$.

Output

Print the minimum number of moves required to finish the game.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq a_i \leq n$
• $a_i \neq a_j$ if $i \neq j$

Example 1

Input:

10
8 10 3 6 5 1 4 7 2 9

Output:

3

Explanation:
The indices of the visited squares are:
$1 \rightarrow 2 \rightarrow 3 \rightarrow 10.$
We can do the last move since $a_{10} = 3 \times a_3.$

Example 2

Input:

10
6 7 10 9 2 1 3 8 4 5

Output:

6

Example 3

Input:

1
1

Output:

0