题目描述

渣朱君最近迷上了狼人杀游戏，他找来小伙伴们在图灵的大教室里围成一圈，每个位置只能坐一个人，他现在想选一个位置把大家集合在一起开始发狼人杀纸牌，但是他希望大家集合的越快越好，每个人都可以按照顺时针或者逆时针的方向移动过去，每移动相邻的两个位置需要$1$个单位时间，由于图灵的大教室没有那么大，所以他的小伙伴们只能沿着位置走，假如所有人收到集合的消息后，立刻以最优的方法向渣朱君选择的位置移动，请你帮他计算一下，要把所有人都集合到一个位置至少需要多长时间？

输入格式

多组输入： 每组数据第一行输入两个数$n,m$。$n$代表图灵教室的座位数，$m$代表渣朱君以及他的小伙伴的总人数。 第二行输入$m$个数，分别代表每一个人初始的位置。

输出格式

每一组数据输出一行，表示所需要的最少时间。

样例

3 2
1 3
5 3
1 4 5

1
1

提示

$1\le n,m \le 1000$

【样例解释】

第一组数据，将第$1、2、3$个位置作为集合点都可以 第二组数据，将第$5$个位置作为集合点