解题思路

模型重述

把每次“手动染黑”看成在时间点 t 出现的一个“源点” a_t。 第 t+1, t+2, … 秒的开始，这个源点会以每秒 1 格的速度向左右扩散。因此，到第 T 秒结束时，这个源点能覆盖的区间为

题目内容

有一条长度为$n$的一维网格(编号为$1$~$n$)。初始时，所有网格均为白色。从第$1$~$m$秒，每一秒结束前会给出一个整数$a_t$,表示将编号为$a_t$的网格手动染成黑色。

同时，过程按秒进行、且在$m$秒之后也继续进行:在每一秒开始时，所有已经为黑色的网格会同时将其左右相邻(编号相差为$1$)的白色网格染成黑色(若相邻位置不存在则忽略)。

请计算:最少经过多少秒结束时，所有网格都被染成黑色。

• 更明确的时间线(同一秒内按如下顺序执行):

  • 在第$t$秒开始时，所有黑色网格同时向左右各扩散$1$格，将相邻白色网格染黑;
  • 若$t≦m$，则在第$t$秒结束前，额外将编号为$a_t$的网格手动染黑(若已为黑色则无额外影响)。

• 在$t>m$时不再有手动染色，但“每秒开始时的扩散”仍持续进行，直到全体网格变黑为止。

你需要输出满足“在第t秒结束时全黑”的最小$t$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T≦10^4)$代表数据组数，每组测试数据描述如下:

第一行输入两个整数$n,m(1≦n≦10^9;1≦m≦2×10^5)$表示网格长度与手动染色的次数;

第二行输入$m$个整数$a_1,a_2,...,a_m (1≦a_i≦n)$表示第$t$秒结束前手动染黑的网格编号。

除此之外，保证单个测试文件的$m$之和不超过$2×10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示在第$t$秒结束时全体网格变黑所需的最少秒数

样例1

输入

2
5 1 
3
10 2
2 9

输出

3
5

说明

初始全白。

对于样例一：

• 第$1$秒结束前手动将3染黑;
• 第$2$秒开始扩散为{$2,3,4$};
• 第3秒开始扩散为{$1,2,3,4,5$}，于是第$3$秒结束时全黑，答案为$3$。

对于样例二：

• 第2秒结束时黑格为{$1,2,3,9$};第$5$秒开始时两端扩散连通覆盖至全体，故第$5$秒结束时全黑,答案为$5$。