题目描述

hsq 在最近在玩一个经营游戏《车位大亨》

在这个游戏中他拥有了一个停车场，这个停车场一共有一排车位，编号为 $1 \sim N$。

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

指定车位的规则是：

每次选择间隔最大的两辆车(你可以认为 $0$ 和 $N + 1$ 也算一辆车，如果有多个间隔长度相同，则选择最靠左的)

然后把车停在两辆车的中间（如果两辆车中间的车位恰好是奇数，则停在正中间，否则停在正中间的左边车位）

不巧的是，这些车主都是特别厉害的主，他们各自有一个心理底线 $a[i]$，一旦有一辆车（不包括 $0$ 和 $N + 1$）跟他的距离小于等于 $a[i]$ 时，他就会无法忍受，跟 hsq 发脾气

同理，如果某个车主被分配的车位一开始就不满足他的心理底线，他就不会在这个停车场停车。

hsq 希望在他开业的第一天，所有客户都能在这停车，于是决定花钱给所有客户进行补偿。

hsq 对某个客户每补偿 $1$ 元钱，就可以让这个客户的心理底线降低 $1$。

现在 hsq 想知道，他最少要花多少钱，才能使得第一天来的所有客户都在他的停车场停车。

P.S. 如果后来的人停在原来的人旁边，使得原来已经在的人不满足心理预期了，那么原来的人也要付钱让他降低心理预期

输入格式

第一行两个数字 $N,M$。

第二行 $M$ 个非负整数表示 $a[i]$。

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

输出格式

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

数据范围

对于 $30\%$ 的数据满足：$1\leq N,M \leq 1000$。

对于 $70\%$ 的数据满足：$1\leq N,M \leq 10^5$。

对于 $100\%$ 的数据满足：$1\leq N \leq 10^{12} , 1\leq M \leq 10^6,0\leq a[i] \leq 10^{12}$

样例输入

10 2
3 3

样例输出

2