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