Jump

Time limit2sMemory limit128 MB

Summary

Find the minimum number of jumps from stone 1 to stone N where jump lengths change by at most 1 each step and some stones are blocked.

Level: Medium5 of 10
Topics: Dynamic programming, BFS, Graph
Solved: No attempts yet

Problem

There are N stones placed at equal intervals. Number them 1, 2, ..., N from left to right. You start on stone 1 and want to reach stone N while following these rules.

Every jump must move forward to a stone with a larger number.
The first jump must be exactly 1 stone, so it moves from stone 1 to stone 2. After that, if the previous jump length was x, the next jump length may be x-1, x, or x+1. Every jump length must be at least 1.
Some stones are too small to stand on.

Find the minimum number of jumps needed to reach stone N from stone 1 while satisfying all rules. If it is impossible, output -1.

Input

The first line contains two integers N and M. N is the number of stones, and M is the number of small stones that cannot be used.

2 <= N <= 10,000, and 0 <= M <= N-2.

Each of the next M lines contains the number of one small stone. Stones 1 and N are always usable.

Output

Output the minimum number of jumps needed to reach stone N. If it is impossible, output -1.

Examples1

Example 1
Input
```
19 3
11
6
16
```
Expected output
```
6
```