← 返回题目列表

Codeforces · 713/E

E. 索尼娅派对制造者

中文机器翻译题面 查看原题

猫头鹰索尼娅决定成为一名派对制造者。为了训练这个角色,她把所有的猫头鹰朋友聚集到乡间别墅里。有 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

注意

在第一个示例中,如果所有猫头鹰都顺时针移动,即沿着索引增加的方向移动,这是可能的。

在示例中,第一只猫头鹰必须顺时针移动,而第二只猫头鹰必须逆时针移动。

在第三个示例中,第一只和第四只猫头鹰应逆时针移动,而第三只和第六只猫头鹰应顺时针移动。第二个和第五个可以向任何方向移动。