猫头鹰索尼娅决定成为一名派对制造者。为了训练这个角色,她把所有的猫头鹰朋友聚集到乡间别墅里。有 m 张椅子围成一圈,编号为 1 到 m 的整数。因此,对于从 1 到 m - 1 的所有 i,椅子 i 和 i + 1 是相邻的。椅子 1 和 m 也是相邻的。有些椅子被她的朋友们占据了。共有 n 个好友。没有两个朋友坐在同一张椅子上。规则如下:
1. 每个参与者从游戏中移走他当前坐的椅子。
2. 每个参与者选择一个她将遵循的方向:顺时针(指数增加,从 m 到 1)和逆时针(指数减少,从 1 到 m)。对于任何一对猫头鹰来说,这个方向可能一致或不同。
3. 每回合所有客人都向所选方向移动一步。如果某个客人移动到那里有椅子的位置,他就会从游戏中移除这张椅子。
4. 如果游戏中没有剩余椅子,则游戏结束。
猫头鹰很忙,想尽快摆脱游戏。他们合作选择方向。您的目标是找到完成游戏所需的最少移动次数。
输入
输入的第一行包含一个整数 m (1 ≤ m ≤ 109) — 圆的长度。
第二行包含一个整数 n (1 ≤ n ≤ 100 000) — 好友数量。
最后一行包含 n 个整数 ai (1 ≤ ai ≤ m) 的递增序列 - 所有猫头鹰的初始位置。
输出
打印完成游戏所需的最小移动数。请注意,0 也可能是答案。
示例
输入 #1
6 3 1 3 5
输出 #1
1
输入 #2
6 2 1 6
输出 #2
2
输入 #3
406 6 1 2 3 204 205 206
输出 #3
100
注意
在第一个示例中,如果所有猫头鹰都顺时针移动,即沿着索引增加的方向移动,这是可能的。
在示例中,第一只猫头鹰必须顺时针移动,而第二只猫头鹰必须逆时针移动。
在第三个示例中,第一只和第四只猫头鹰应逆时针移动,而第三只和第六只猫头鹰应顺时针移动。第二个和第五个可以向任何方向移动。