Problem Description

In Takahashi Railway, some parts of a train with $ N $ cars have broken down, so $ M $ maintenance workers will inspect them.

The $ i $-th maintenance worker initially is at the $ X_i $-th car. Each maintenance worker can inspect the current car or move to an adjacent car. Inspecting a car takes no time, but moving to an adjacent car takes $ 1 $ minute.

The inspection work is considered complete when all cars have been inspected by at least one maintenance worker. What is the minimum time required to complete the inspection work?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ X_1 $ $ X_2 $ : $ X_M $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 10^9),\ M\ (1\ ≦\ M\ ≦\ 10^5,\ M\ ≦\ N)$ separated by a space. This indicates that the train consists of $ N $ cars and there are $ M $ maintenance workers.
• The next $ M $ lines provide information about the maintenance workers. The $i\ (1\ ≦\ i\ ≦\ M)$-th line contains an integer $X_i\ (1\ ≦\ X_i\ ≦\ N)$. This indicates that the $ i $-th maintenance worker initially is at the $ X_i $-th car. It is guaranteed that all $ X_i $ are distinct and the information is given in the order from the closest to the first car, i.e., $X_j\ <\ X_{j+1}\ (1\ ≦\ j\ ≦\ M-1)$.

Output Format

Output the minimum time in minutes required for the inspection work on one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

17 5
1
5
10
15
16

Sample Output #1

3

Sample Input #2

66 10
8
9
16
23
37
47
51
52
53
64

Sample Output #2

8

Notes/Hints

Partial Points

This problem has partial points:

• If you solve the dataset where $N\ ≦\ 100$, you will be awarded $ 20 $ points.
• If you solve the dataset where $N\ ≦\ 500,000$, you will be awarded an additional $ 60 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 20 $ points.

Sample Explanation 1

The inspection work can be completed in $ 3 $ minutes by moving the maintenance workers as shown in the figure below.

见题面 Input 部分

见题面 Output 部分