又双叒叕没中奖1

午客网常常举办算法竞赛, 为了吸引大家参赛, 会在通过题目的人中随机抽取一些人获得奖品

有n个人参加了这场比赛并通过了至少一道题目, 午客网将从中抽取m个人获得奖品

假设这n个人的比赛排名分别为1到n, 且没有并列的情况, 午客网随机抽出了排名为的参赛选手获得奖品

然而没有抽到奖的人都纷纷抱怨: "只差x名就中奖了!"

虾部长想知道: 离中奖距离最远的人"只差多少名就中奖了"? 聪明的你能帮帮他吗?

如果某人的排名为k, 那么他与中奖的距离定义为: ，即: 该排名与所有中奖排名的差值的最小值

每个文件仅包含一组测试数据

第一行包含2个正整数n,m (1≤m≤10⁵且m≤n≤10⁹), 含义如题面所述

第二行包含m个正整数a₁,a₂,a₃,…,a_i,…,a_m (1≤a_i≤n且互不相同, 不保证按升序排列), 含义如题面所述

输出仅包含一个非负整数, 表示中奖距离最远的人的中奖距离

3 1
1

2



Notes
排名第三的人差2名就中奖了