该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$TooY0ung$ 花重金收购了一个停车场。

停车场一共有一排车位，编号为 $1$ ~ $N$。

$TooY0ung$不希望自己的停车场看起来过于拥挤， 因此，$TooY0ung$ 会给每个来停车的客户指定车位。

指定车位的规则是：

选择间隔最大的两辆车(你可以认为 $0$ 和 $N+1$ 也算一辆车，如果有多个间隔一样，则选择最靠左的)，然后把车停在两辆车的中间（如果两辆车中间的车位恰好是奇数，则停在正中间，否则停在正中间的左边车位）。

不巧的是，这些车主都是不好打搅的主，他们各自有一个心理底线 $a_i$，一旦有一辆车（不包括 $0$ 和 $N+1$ ）跟他的距离小于等于 $a_i$ 时，他就会无法忍受，直接开车离去。

同理，如果他被分配的车位一开始就不满足要求，他就不会在这个停车场停车。

$TooY0ung$ 希望在开业的第一天，所有客户都能在这停车，于是决定用钱收买他们。

确切的说，$TooY0ung$ 每花 $1$ 元，可以让一个客户的心理底线下降 $1$。

现在的问题是，$TooY0ung$ 最少要花多少钱，才能使得所有客户都在他的停车场停车。

输入格式

第一行输入两个数字 $n$ 和 $m$，$n$ 是停车场车位数，$m$ 是客户数。

第二行输入 $m$ 个非负整数，表示 $a_i$。

保证这 $m$ 个客户都是按顺序来停车的。

输出格式

输出包含一行，一个整数，表示答案。

10 2
3 3

2

样例解释

第一个人停在了 $5$，第二个人停在了 $8$，他们两个人互相嫌弃，$TooY0ung$ 一人给了 $1$ 块钱，问题解决。

数据规模与约定

对于 $30\%$ 的数据：$1 \le n,m \le 1000$。

对于 $70\%$ 的数据：$1 \le n,m \le 10^5$。

对于所有测试点：$1 \le n \le 10^{12}，1 \le m \le 10^6，0 \le a[i] \le 10^{12}$。