A. Water The Garden

problem_index: A

time_limit: 1 second

memory_limit: 256 megabytes

input_spec:
The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 200).
Then t test cases follow. The first line of each test case contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n) — the number of garden beds and water taps, respectively.
Next line contains k integers xi (1 ≤ xi ≤ n) — the location of i-th water tap. It is guaranteed that for each ![image](images/cf_920_A/3.png) condition xi - 1 < xi holds.
It is guaranteed that the sum of n over all test cases doesn't exceed 200.
Note that in hacks you have to set t = 1.

solutions: ["t = int(input())\nfor tc in range(t):\n\t(n, k) = map(int, input().split())\n\ttap = list(map(int, input().split()))\n\tsol = 0\n\tfor i in range(1, n + 1):\n\t\td = 1000000\n\t\tfor j in tap:\n\t\t\td = min(d, abs(j - i) + 1)\n\t\tsol = max(sol, d)\n\tprint(sol)\n", "t = int(input())\nwhile t > 0:\n\tt -= 1\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tans = 0\n\tans = max(a[0], n - a[-1] + 1)\n\tl = len(a)\n\tfor i in range(l - 1):\n\t\tans = max(int((a[i + 1] - a[i]) / 2 + 1), ans)\n\tprint(ans)\n", "import math\nt = int(input())\ninputs = []\nfor _ in range(t):\n\tline = input().split(' ')\n\t(n, k) = (int(line[0]), int(line[1]))\n\txs = [int(i) for i in input().split(' ')]\n\tinputs.append([n, k, xs])\nfor ele in inputs:\n\t(n, k, xs) = ele\n\tresult = 0\n\tfor i in range(k):\n\t\tif i == 0:\n\t\t\tresult = max(result, xs[i] - 0)\n\t\telse:\n\t\t\tresult = max(result, math.floor((xs[i] - xs[i - 1]) / 2) + 1)\n\t\tif i == k - 1:\n\t\t\tresult = max(result, n + 1 - xs[i])\n\tprint(result)\n", "t = int(input())\nfor mmm in range(t):\n\t(n, m) = map(int, input().split())\n\ttime = 0\n\twa = [i - 1 for i in map(int, input().split())]\n\ta = [0 for i in range(n)]\n\tfor i in wa:\n\t\ta[i] = 1\n\twhile a.count(1) != len(a):\n\t\ttime += 1\n\t\tj = 0\n\t\tb = a.copy()\n\t\twhile j < n:\n\t\t\tif b[j] == 1 and j != 0 and (j != n - 1):\n\t\t\t\t(a[j - 1], a[j + 1]) = (1, 1)\n\t\t\telif b[j] == 1 and j == 0:\n\t\t\t\ta[j + 1] = 1\n\t\t\telif b[j] == 1 and j == n - 1:\n\t\t\t\ta[j - 1] = 1\n\t\t\tj += 1\n\tprint(time + 1)\n", "def main():\n\tfor _ in range(int(input())):\n\t\t(n, k) = map(int, input().split())\n\t\t(a, *bb) = map(int, input().split())\n\t\tr = a * 2 - 1\n\t\tfor b in bb:\n\t\t\tif r < b - a:\n\t\t\t\tr = b - a\n\t\t\ta = b\n\t\tif r < (n - a) * 2 + 1:\n\t\t\tr = (n - a) * 2 + 1\n\t\tprint(r // 2 + 1)\nmain()\n", "for _ in range(int(input().strip())):\n\t(n, k) = map(int, input().split())\n\tar = [0] * n\n\twater = [int(p) for p in input().split()]\n\tt = 1\n\tcounter = 0\n\tl = []\n\tr = []\n\tfor i in water:\n\t\tar[i - 1] = 1\n\t\tif i - 2 >= 0:\n\t\t\tl.append(i - 2)\n\t\tif i < n:\n\t\t\tr.append(i)\n\twhile True:\n\t\tfor i in range(n):\n\t\t\tif not ar[i]:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tcounter = 1\n\t\tif counter:\n\t\t\tbreak\n\t\tp = []\n\t\tfor i in range(len(l)):\n\t\t\tp.append(i)\n\t\t\tar[l[i]] = 1\n\t\t\tif l[i] - 1 >= 0:\n\t\t\t\tl.append(l[i] - 1)\n\t\tp.sort()\n\t\tp.reverse()\n\t\tfor i in p:\n\t\t\tl.pop(i)\n\t\tp = []\n\t\tfor i in range(len(r)):\n\t\t\tp.append(i)\n\t\t\tar[r[i]] = 1\n\t\t\tif r[i] + 1 < n:\n\t\t\t\tr.append(r[i] + 1)\n\t\tp.sort()\n\t\tp.reverse()\n\t\tfor i in p:\n\t\t\tr.pop(i)\n\t\tt += 1\n\tprint(t)\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = []\n\tl = list(map(int, input().split()))\n\ttaps.append(l[0])\n\tx = l[0]\n\tfor y in l[1:]:\n\t\ttaps.append(math.ceil((y - (x - 1)) / 2))\n\t\tx = y\n\ttaps.append(n - x + 1)\n\tprint(max(taps))\n", "for _ in range(int(input().strip())):\n\t(n, k) = map(int, input().split())\n\tar = [int(p) for p in input().split()]\n\tar.sort()\n\tmaxim = max(ar[0] - 0 - 1, n - ar[-1])\n\tfor i in range(1, k):\n\t\tt = (ar[i] - ar[i - 1]) // 2\n\t\tif t > maxim:\n\t\t\tmaxim = t\n\tprint(maxim + 1)\n", "tc = int(input())\nwhile tc:\n\ttc -= 1\n\tinfo = input().split(' ')\n\tn = int(info[0])\n\tk = int(info[1])\n\tinfo = input().split(' ')\n\tx = []\n\tfor i in range(0, k):\n\t\tx.append(int(info[i]))\n\tans = 0\n\tfor i in range(1, k):\n\t\tans = max(ans, (x[i] - x[i - 1]) // 2 + 1)\n\tans = max(ans, x[0])\n\tans = max(ans, n - x[k - 1] + 1)\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tcont = 0\n\tr = 0\n\tb = [0 for i in range(n)]\n\twhile cont < n:\n\t\tr += 1\n\t\tfor i in a:\n\t\t\tif b[max(0, i - r)] == 0:\n\t\t\t\tcont += 1\n\t\t\t\tb[max(0, i - r)] = 1\n\t\t\tif b[min(n - 1, i + r - 2)] == 0:\n\t\t\t\tcont += 1\n\t\t\t\tb[min(n - 1, i + r - 2)] = 1\n\tprint(r)\n", "t = int(input())\nfor i in range(0, t):\n\t(n, k) = str(input()).split()\n\t(n, k) = (int(n), int(k))\n\twbeds = set()\n\tnewbeds = set()\n\tnb = set()\n\tks = str(input()).split()\n\tfor i in ks:\n\t\tnewbeds.add(int(i))\n\ttime = 0\n\twhile True:\n\t\tfor i in newbeds:\n\t\t\twbeds.add(i)\n\t\ttime += 1\n\t\tif len(wbeds) == n:\n\t\t\tbreak\n\t\tfor i in newbeds:\n\t\t\tif 1 < i < n:\n\t\t\t\tnb.add(i - 1)\n\t\t\t\tnb.add(i + 1)\n\t\t\tif i == 1:\n\t\t\t\tnb.add(i + 1)\n\t\t\tif i == n:\n\t\t\t\tnb.add(i - 1)\n\t\tnewbeds = set()\n\t\tfor i in nb:\n\t\t\tnewbeds.add(i)\n\tprint(time)\n", "for jiwojdilanmdw in range(int(input())):\n\t(n, k) = [int(x) for x in input().split()]\n\tM = 0\n\tl = [int(x) for x in input().split()]\n\tfor i in range(1, k):\n\t\tif l[i] - l[i - 1] > M:\n\t\t\tM = l[i] - l[i - 1]\n\telse:\n\t\tM = M // 2 + 1\n\tprint(max(l[0], M, n - l[-1] + 1))\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = input().split(' ')\n\tn = int(n)\n\tk = int(k)\n\tarr = input().split(' ')\n\tif n == k:\n\t\tprint(1, '\\n')\n\t\tcontinue\n\tfor j in range(len(arr)):\n\t\tarr[j] = int(arr[j])\n\tmaxi = 0\n\tfor j in range(1, k):\n\t\tif arr[j] - arr[j - 1] - 1 > maxi:\n\t\t\tmaxi = arr[j] - arr[j - 1] - 1\n\tmaxi = math.ceil(maxi / 2.0) + 1\n\tif arr[0] > maxi:\n\t\tmaxi = arr[0]\n\tif n - arr[len(arr) - 1] + 1 > maxi:\n\t\tmaxi = n - arr[len(arr) - 1] + 1\n\tprint(maxi)\n", "import sys, math, queue, bisect\nMOD = 10 ** 9 + 7\nsys.setrecursionlimit(1000000)\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tw = [False for i in range(n)]\n\tfor ki in map(int, input().split()):\n\t\tw[ki - 1] = True\n\tt = 1\n\twhile not all(w):\n\t\tt += 1\n\t\tnw = []\n\t\tfor i in range(n):\n\t\t\tif 0 < i:\n\t\t\t\tif w[i - 1]:\n\t\t\t\t\tnw.append(i)\n\t\t\tif i < n - 1:\n\t\t\t\tif w[i + 1]:\n\t\t\t\t\tnw.append(i)\n\t\tfor nwi in nw:\n\t\t\tw[nwi] = True\n\tprint(t)\n", "t = list(map(int, input().strip().split()))[0]\nfor i in range(t):\n\t(n, p) = list(map(int, input().strip().split()))\n\tdp = dict()\n\tfor i in range(1, n + 1):\n\t\tdp[i] = 1\n\tk = list(map(int, input().strip().split()))\n\tplus = []\n\tminus = []\n\tfor j in k:\n\t\tplus.append(j)\n\t\tminus.append(j)\n\tsecond = 0\n\twhile len(dp) > 0:\n\t\tfor i in plus:\n\t\t\tif i + second in dp:\n\t\t\t\tdp.pop(i + second)\n\t\tfor i in minus:\n\t\t\tif i - second in dp:\n\t\t\t\tdp.pop(i - second)\n\t\tsecond += 1\n\tprint(second)\n", "t = int(input())\nfor test in range(t):\n\t(n, k) = list(map(int, input().split()))\n\tposs = list(map(int, input().split()))\n\tres = max(poss[0], n - poss[-1] + 1)\n\tfor i in range(1, k):\n\t\tres = max(res, (poss[i] - poss[i - 1] + 2) // 2)\n\tprint(res)\n", "def findShort(n, k, pos, result):\n\tpos.insert(0, 0)\n\tans = max(pos[1] - 1, n - pos[k])\n\tfor i in range(2, k + 1):\n\t\ttemp = pos[i] - pos[i - 1] - 1\n\t\tif temp % 2:\n\t\t\ttemp = int(temp / 2) + 1\n\t\telse:\n\t\t\ttemp = int(temp / 2)\n\t\tans = max(ans, temp)\n\tresult.append(ans + 1)\n\ndef main():\n\tt = int(input())\n\tresult = []\n\tfor i in range(t):\n\t\tinputLine = input()\n\t\t(n, k) = inputLine.split()\n\t\tpositionInput = input()\n\t\tpos = positionInput.split()\n\t\tfindShort(int(n), int(k), list(map(int, pos)), result)\n\tfor i in result:\n\t\tprint(i)\nmain()\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = list(map(int, str(input()).split()))\n\ta = list(map(int, str(input()).split()))\n\tans = max(a[0], n - a[k - 1] + 1)\n\tfor i in range(1, k):\n\t\tans = max(ans, (a[i] - a[i - 1] + 2) // 2)\n\tprint(ans)\n", "import sys\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tans = max(a[0], n - a[-1] + 1)\n\tfor (x, y) in zip(a, a[1:]):\n\t\tans = max(ans, 1 + (y - x) // 2)\n\tprint(ans)\n", "t = int(input())\nfor T in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tres = max(a[0], n - a[-1] + 1)\n\tlast = a[0]\n\tfor x in a[1:]:\n\t\tres = max(res, 1 + (x - last) // 2)\n\t\tlast = x\n\tprint(res)\n", "from sys import stdin, stdout\n\ndef rint():\n\treturn map(int, stdin.readline().split())\nt = int(input())\nfor i in range(t):\n\t(n, k) = rint()\n\tx = []\n\tx = list(rint())\n\tans = 0\n\tans = max(ans, x[0])\n\tans = max(ans, n - x[-1] + 1)\n\tif k < 1:\n\t\tprint(ans)\n\t\tcontinue\n\tfor ii in range(0, k - 1):\n\t\tans = max(ans, (x[ii + 1] - x[ii]) // 2 + 1)\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tw = list(map(int, input().split()))\n\tlst1 = [w[0], n - w[-1] + 1]\n\tlst2 = [(w[i + 1] - w[i]) // 2 + 1 for i in range(k - 1)]\n\tprint(max(lst1 + lst2))\n", "t = int(input())\nwhile t:\n\t(n, k) = [int(x) for x in input().split()]\n\tl = [int(x) for x in input().split()]\n\tm = -1\n\tfor i in range(k):\n\t\tif i > 0:\n\t\t\tif m < l[i] - l[i - 1]:\n\t\t\t\tm = l[i] - l[i - 1]\n\tp = l[0]\n\tif l[0] < n - l[k - 1] + 1:\n\t\tp = n - l[k - 1] + 1\n\tif m // 2 + 1 < p:\n\t\tprint(p, '\\n')\n\telse:\n\t\tprint(m // 2 + 1, '\\n')\n\tt = t - 1\nquit()\n", "t = int(input())\nwhile t > 0:\n\t(n, k) = map(int, input().split(' '))\n\tx = list(map(int, input().split(' ')))\n\tnList = list((0 if i not in x else 1 for i in range(1, n + 1)))\n\ts = 1\n\twhile 0 in nList:\n\t\tnList = [1 if i > 0 and nList[i - 1] == 1 or (i < len(nList) - 1 and nList[i + 1] == 1) else nList[i] for i in range(len(nList))]\n\t\ts += 1\n\tprint(s)\n\tt -= 1\n", "import math\nfor _ in range(int(input())):\n\t(n, m) = map(int, input().split())\n\tk = [int(i) for i in input().split()]\n\tstart = k[0]\n\tmaxcount = 0\n\tfor x in k[1:]:\n\t\tmaxcount = max(math.ceil((x - start - 1) / 2) + 1, maxcount)\n\t\tstart = x\n\tmaxcount = max(k[0], maxcount)\n\tmaxcount = max(n - k[-1] + 1, maxcount)\n\tprint(maxcount)\n", "nums = int(input())\nfor _ in range(nums):\n\t(length, num) = map(int, input().split())\n\tlistA = list(map(int, input().split()))\n\t(maxA, maxB) = (0, 0)\n\tif length == num:\n\t\tprint(1)\n\telif num == 1:\n\t\tprint(max(length - listA[0] + 1, listA[0]))\n\telse:\n\t\tmaxB = max(length - listA[-1] + 1, listA[0])\n\t\tfor i in range(len(listA) - 1):\n\t\t\tmaxA = max(listA[i + 1] - listA[i], maxA)\n\t\tmaxA = int(maxA / 2) + 1\n\t\tprint(max(maxA, maxB))\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = [int(x) for x in input().split()]\n\tresult = 0\n\tfor i in range(1, n + 1):\n\t\tbest = n + 1\n\t\tfor x in taps:\n\t\t\tbest = min([best, abs(x - i)])\n\t\tresult = max([result, best])\n\tprint(result + 1)\n", "from bisect import bisect\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tar = set(map(int, input().split()))\n\tans = 0\n\tfor i in range(n):\n\t\tr = i\n\t\twhile r >= 0:\n\t\t\tif r + 1 in ar:\n\t\t\t\tbreak\n\t\t\tr -= 1\n\t\tif r == -1:\n\t\t\tr = -float('inf')\n\t\tl = i\n\t\twhile l < n:\n\t\t\tif l + 1 in ar:\n\t\t\t\tbreak\n\t\t\tl += 1\n\t\tif l == n:\n\t\t\tl = float('inf')\n\t\tans = max(ans, min(i - r, l - i))\n\tprint(ans + 1)\n", "I = lambda : [*map(int, input().split())]\nfor _ in [0] * I()[0]:\n\t(n, k) = I()\n\tx = I()\n\tr = max(x[0] - 1, n - x[k - 1])\n\tfor i in range(1, k):\n\t\tr = max(r, x[i] - x[i - 1] >> 1)\n\tprint(r + 1)\n", "def true_array(b):\n\tfor i in range(len(b)):\n\t\tif b[i] == 0:\n\t\t\treturn 0\n\treturn 1\nt = int(input())\nfor q in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tb = [0 for i in range(n)]\n\tt = 0\n\twhile true_array(b) != 1:\n\t\tfor m in a:\n\t\t\tfor i in range(max(m - t - 1, 0), min(m + t, n)):\n\t\t\t\tb[i] = 1\n\t\tt += 1\n\tprint(t)\n", "t = int(input())\nfor tt in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tm = max(a[0], n + 1 - a[k - 1])\n\tfor i in range(1, k):\n\t\tm = max(m, (a[i] - a[i - 1]) // 2 + 1)\n\tprint(m)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = input().split()\n\ta = list(map(int, a))\n\tans = 0\n\tfor j in range(k):\n\t\tif j == 0:\n\t\t\tans = max(ans, a[j])\n\t\telse:\n\t\t\tans = max(ans, (a[j] - a[j - 1] + 2) // 2)\n\t\tif j == k - 1:\n\t\t\tans = max(ans, n - a[j] + 1)\n\t\telse:\n\t\t\tans = max(ans, (a[j + 1] - a[j] + 2) // 2)\n\tprint(ans)\n", "import math\nt = int(input())\nans = []\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = input().split()\n\tfor i in range(k):\n\t\ttaps[i] = int(taps[i])\n\tmax_time = 0\n\tfor i in range(n):\n\t\tmin_time = 1000\n\t\tfor j in range(k):\n\t\t\tmin_time = min(min_time, int(math.fabs(i + 1 - taps[j])))\n\t\tmax_time = max(max_time, min_time)\n\tans.append(max_time)\nfor i in range(t):\n\tprint(ans[i] + 1)\n", "import math\nt = int(input())\na = []\nfor _ in range(t):\n\t(n, k) = list(map(int, input().strip().split(' ')))\n\tarr = list(map(int, input().strip().split(' ')))\n\tres = arr[0] - 1\n\tfor i in range(1, k):\n\t\tif math.floor((arr[i] - arr[i - 1]) / 2) > res:\n\t\t\tres = math.floor((arr[i] - arr[i - 1]) / 2)\n\tif n - arr[-1] > res:\n\t\tres = n - arr[-1]\n\tprint(res + 1)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = [int(x) for x in input().split()]\n\tKrList = [int(x) for x in input().split()]\n\tmaxl = max(KrList[0], n - KrList[-1] + 1)\n\tfor K in range(k - 1):\n\t\tmaxl = max(maxl, (KrList[K + 1] - KrList[K]) // 2 + 1)\n\tprint(maxl)\n", "INF = 10 ** 10\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\txi = 0\n\tbeds = [[INF, INF] for i in range(n)]\n\tfor i in range(n):\n\t\tif xi < k and i + 1 == x[xi]:\n\t\t\tbeds[i][0] = 1\n\t\t\txi += 1\n\t\telif i != 0:\n\t\t\tbeds[i][0] = beds[i - 1][0] + 1\n\txi -= 1\n\tfor i in range(n - 1, -1, -1):\n\t\tif xi >= 0 and i + 1 == x[xi]:\n\t\t\tbeds[i][1] = 1\n\t\t\txi -= 1\n\t\telif i != n - 1:\n\t\t\tbeds[i][1] = beds[i + 1][1] + 1\n\tfor i in range(n):\n\t\tbeds[i] = min(beds[i])\n\tprint(max(beds))\n", "t = int(input())\nfor i in range(t):\n\t[n, k] = [int(x) for x in input().split()]\n\tans = 1\n\txi = [int(x) for x in input().split()]\n\tans = xi[0]\n\tfor j in range(1, k):\n\t\tif (xi[j] - xi[j - 1] + 2) // 2 > ans:\n\t\t\tans = (xi[j] - xi[j - 1] + 2) // 2\n\tif n - xi[k - 1] + 1 > ans:\n\t\tans = n - xi[k - 1] + 1\n\tprint(ans)\n", "for i in range(int(input())):\n\t(n, k) = map(int, map(int, input().split()))\n\ta = list(map(int, input().split()))\n\tx = 0\n\tm = max(a[0], n - a[-1] + 1)\n\tfor i in range(k - 1):\n\t\tif (a[i + 1] - a[i] + 2) // 2 > m:\n\t\t\tm = (a[i + 1] - a[i] + 2) // 2\n\tprint(m)\n", "import math as m\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(n, k) = map(int, input().split(' '))\n\t\txs = list(map(int, input().split(' ')))\n\t\tfirst_d = xs[0]\n\t\tlast_d = n - xs[-1] + 1\n\t\tres = max(first_d, last_d)\n\t\tif k >= 2:\n\t\t\tres = max(res, max([m.floor((xs[i + 1] - xs[i]) / 2 + 1) for i in range(k - 1)]))\n\t\tprint(int(res))\nmain()\n", "for i in range(int(input())):\n\t(n, k) = (int(i) for i in input().split())\n\tloc = [int(j) for j in input().split()]\n\tx = max([n - max(loc)] + [min(loc) - 1] + [(loc[j + 1] - loc[j]) // 2 for j in range(k - 1)])\n\tprint(x + 1)\n", "tests = int(input())\nfor t in range(tests):\n\t(n, k) = map(int, input().split())\n\togrod = []\n\tfor i in range(n):\n\t\togrod.append(0)\n\ttaps = input().split()\n\tfor i in range(k):\n\t\togrod[int(taps[i]) - 1] = 1\n\tczas = 1\n\tporownanie = []\n\tfor x in ogrod:\n\t\tporownanie.append(x)\n\twhile 0 in ogrod:\n\t\tfor i in range(n):\n\t\t\tif i > 0 and ogrod[i] == 1:\n\t\t\t\tporownanie[i - 1] = 1\n\t\t\tif i < n - 1 and ogrod[i] == 1:\n\t\t\t\tporownanie[i + 1] = 1\n\t\tczas += 1\n\t\tfor i in range(n):\n\t\t\togrod[i] = porownanie[i]\n\tprint(czas)\n", "test = int(input())\nfor i in range(0, test):\n\t(n, k) = map(int, input().split(' '))\n\ta = list(map(int, input().split(' ')))\n\tt = 1\n\tl = [0] * n\n\tfor j in range(0, k):\n\t\tl[a[j] - 1] = 1\n\twhile l.count(1) != n:\n\t\tfor j in range(0, k):\n\t\t\tl[min(n - 1, a[j] - 1 + t)] = 1\n\t\t\tl[max(0, a[j] - 1 - t)] = 1\n\t\tt += 1\n\tprint(t)\n", "num_of_examples = int(input())\nnum_of_bed_list = []\nindex_of_water_list = []\nfor _ in range(num_of_examples):\n\tnum_of_bed = int(input().split(' ')[0])\n\tnum_of_bed_list.append(num_of_bed)\n\tindex_of_water = input().split(' ')\n\tindex_of_water = [int(x) for x in index_of_water]\n\tindex_of_water_list.append(index_of_water)\nfor i in range(len(num_of_bed_list)):\n\tresult = []\n\tmedium_time_list = []\n\tlen_of_garden = num_of_bed_list[i]\n\tindex_of_water = index_of_water_list[i]\n\tleft_time = index_of_water[0]\n\tright_time = len_of_garden + 1 - index_of_water[-1]\n\tif len(index_of_water) != 1:\n\t\tfor j in range(len(index_of_water) - 1):\n\t\t\tmedium_time = (index_of_water[j + 1] - index_of_water[j]) // 2 + 1\n\t\t\tmedium_time_list.append(medium_time)\n\t\t\tmedium_time_max = max(medium_time_list)\n\t\tresult.append(left_time)\n\t\tresult.append(right_time)\n\t\tresult.append(medium_time_max)\n\telse:\n\t\tresult.append(left_time)\n\t\tresult.append(right_time)\n\ttime_used = max(result)\n\tprint(time_used)\n", "import math\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tif k == 1:\n\t\tprint(max(n - a[0], a[0] - 1) + 1)\n\telif k == n:\n\t\tprint(1)\n\telse:\n\t\t(x, y, h) = (a[0] - 1, n - a[-1], 0)\n\t\tfor i in range(k - 1):\n\t\t\tif a[i + 1] - a[i] - 1 > h:\n\t\t\t\th = a[i + 1] - a[i] - 1\n\t\tz = math.ceil(h / 2)\n\t\tprint(max(x, max(y, z)) + 1)\n", "def fill(empty, k, i):\n\tempty[k] = 1\n\tif k - i >= 0:\n\t\tempty[k - i] = 1\n\tif k + i <= len(empty) - 1:\n\t\tempty[k + i] = 1\n\ndef testfull(empty):\n\tfor i in range(0, len(empty)):\n\t\tif empty[i] == 0:\n\t\t\treturn False\n\treturn True\n\ndef solve(tap, inn):\n\tempty = [0] * inn[0]\n\ti = 0\n\twhile testfull(empty) == False:\n\t\tfor k in tap:\n\t\t\tfill(empty, k, i)\n\t\ti = i + 1\n\treturn str(i)\nn = int(input())\nfor i in range(0, n):\n\tinn = input().split(' ')\n\tinnInt = [int(x) for x in inn]\n\ttap = input().split(' ')\n\ttapInt = [int(x) - 1 for x in tap]\n\tprint(solve(tapInt, innInt))\n", "T = int(input())\nfor _ in range(T):\n\t(n, k) = map(int, input().split(' '))\n\ttap = list(map(int, input().split(' ')))\n\tbed = [0] * n\n\tif n == k:\n\t\tprint(1)\n\telse:\n\t\tcount = 0\n\t\tflag = 0\n\t\twhile True:\n\t\t\tfor i in tap:\n\t\t\t\tfor j in range(max(0, i - count - 1), min(i + count, n)):\n\t\t\t\t\tbed[j] = 1\n\t\t\t\tif sum(bed) == n:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tprint(count + 1)\n\t\t\t\t\tbreak\n\t\t\tcount += 1\n\t\t\tif flag == 1:\n\t\t\t\tbreak\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tprint(max([(x[i + 1] - x[i]) // 2 for i in range(k - 1)] + [x[0] - 1, n - x[-1]]) + 1)\n", "from math import *\nfrom collections import *\nt = int(input())\nfor y in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\ta.sort()\n\tm = max(a[0], n + 1 - a[k - 1])\n\tfor i in range(k - 1):\n\t\tm = max(m, ceil((a[i + 1] - a[i] + 1) / 2))\n\tprint(m)\n", "import sys\nimport math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\th = [0 for i in range(n)]\n\ttm = 0\n\twhile 1:\n\t\tfor j in x:\n\t\t\tif j - tm - 1 >= 0:\n\t\t\t\th[j - tm - 1] = 1\n\t\t\tif j + tm - 1 < n:\n\t\t\t\th[j - 1 + tm] = 1\n\t\tif sum(h) == n:\n\t\t\tprint(tm + 1)\n\t\t\tbreak\n\t\ttm += 1\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\ts = set(l)\n\tb = set(range(1, n + 1))\n\tc = 1\n\twhile b - s != set():\n\t\tfor j in range(k):\n\t\t\ts.add(l[j] + c)\n\t\t\ts.add(l[j] - c)\n\t\tc += 1\n\tprint(c)\n", "def time_spend(x, y, L):\n\tif x - L[-1] > L[0] - 1:\n\t\tmaxdis = x - L[-1]\n\telse:\n\t\tmaxdis = L[0] - 1\n\tfor i in range(y - 1):\n\t\tmax_temp = location[i + 1] - location[i]\n\t\tif max_temp // 2 > maxdis:\n\t\t\tmaxdis = max_temp // 2\n\treturn maxdis + 1\nt = int(input())\nresult = []\nfor i in range(t):\n\t(n, k) = input().split()\n\tn = int(n)\n\tk = int(k)\n\tlocation = list(map(int, input().strip().split()))\n\tresult.append(time_spend(n, k, location))\nfor i in range(t):\n\tprint(result[i])\n", "def resolve(n, k, k_list):\n\tr = n - k\n\tif r < 2:\n\t\treturn r + 1\n\tk_list.sort()\n\tl = k_list[0]\n\tr = n - k_list[-1] + 1\n\tlr_max = l if l > r else r\n\tif k > 1:\n\t\tk_list = [k_list[j + 1] - k_list[j] for j in range(k - 1)]\n\t\tk_max = max(k_list) // 2 + 1\n\t\tr = lr_max if lr_max > k_max else k_max\n\t\treturn r\n\telse:\n\t\treturn lr_max\nres = []\nt = int(input())\nfor i in range(t):\n\t(N, K) = map(int, input().split())\n\tK_list = list(map(int, input().split()))\n\tres.append(resolve(N, K, K_list))\nres = '\\n'.join([str(i) for i in res])\nprint(res)\n", "t = int(input())\nfrom math import ceil\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\tz = float('-inf')\n\tfor j in range(len(l)):\n\t\tif j == 0:\n\t\t\tz = max(l[j], z)\n\t\tif j < k - 1:\n\t\t\tz = max(ceil((l[j + 1] - l[j] - 1) / 2) + 1, z)\n\t\tif j == k - 1:\n\t\t\tz = max(n - l[j] + 1, z)\n\tprint(z)\n", "t = int(input())\nans = []\nfor i in range(t):\n\t(n, k) = [int(z) for z in input().split()]\n\ta = [int(z) for z in input().split()]\n\tmaxdist = -1000000\n\tfor i in range(k - 1):\n\t\tmaxdist = max(maxdist, a[i + 1] - a[i])\n\tmaxdist = maxdist // 2\n\tif maxdist < max(a[0] - 1, n - a[k - 1]):\n\t\tkek = max(a[0] - 1, n - a[k - 1])\n\telse:\n\t\tkek = maxdist\n\tans.append(kek + 1)\nfor i in ans:\n\tprint(i)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\togorod = [0] * n\n\tsec = 0\n\twhile not all(ogorod):\n\t\tsec += 1\n\t\tfor xi in x:\n\t\t\tfor j in range(1, sec):\n\t\t\t\tif xi - 1 - j >= 0:\n\t\t\t\t\togorod[xi - 1 - j] += 1\n\t\t\t\tif xi - 1 + j < n:\n\t\t\t\t\togorod[xi - 1 + j] += 1\n\t\t\togorod[xi - 1] += 1\n\tprint(sec)\n", "t = int(input())\nfor i in range(t):\n\ts = input().split(' ')\n\tn = int(s[0])\n\tk = int(s[1])\n\ts = input().split(' ')\n\tarr = []\n\tfor l in s:\n\t\tarr.append(int(l))\n\tanswer = arr[0]\n\tfor j in range(0, k - 1):\n\t\tdist = (arr[j + 1] - arr[j]) // 2 + 1\n\t\tanswer = max(answer, dist)\n\tanswer = max(answer, n - arr[k - 1] + 1)\n\tprint(answer)\n", "t = int(input())\nx = []\ny = []\nfor i in range(t):\n\t(n, k) = (int(x) for x in input().split())\n\ty.append([n, k])\n\tx.append([int(x) for x in input().split()])\nfor (j, i) in enumerate(x):\n\tp0 = i[0] - 1\n\tpp = y[j][0] - i[-1]\n\th = [p0, pp]\n\tfor i1 in range(len(i) - 1):\n\t\th.append(abs(i[i1] - i[i1 + 1]) // 2)\n\tprint(max(h) + 1)\n", "import math\nn = int(input())\nfor i in range(0, n):\n\t(n, k) = input().split()\n\tn = int(n)\n\tk = int(k)\n\ty = list(map(int, input().split()))\n\tx = y[0]\n\to = len(y) - 1\n\tfor j in range(1, len(y)):\n\t\ta = math.floor((y[j] - y[j - 1]) / 2) + 1\n\t\tif a > x:\n\t\t\tx = a\n\tif n - y[o] >= x:\n\t\tb = n - y[o] + 1\n\t\tx = b\n\tprint(x)\n", "t = int(input())\nwhile t:\n\tt -= 1\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\ttm = 0\n\tfor i in range(1, n + 1):\n\t\ttmm = 10000\n\t\tfor j in a:\n\t\t\ttmm = min(tmm, abs(j - i) + 1)\n\t\ttm = max(tm, tmm)\n\tprint(tm)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tf = [0] * (n + 1)\n\tf[0] = 1\n\ta = list(map(int, input().split()))\n\tnum = 0\n\twhile min(f) == 0:\n\t\tfor j in range(k):\n\t\t\tf[min(a[j] + num, n)] += 1\n\t\t\tf[max(a[j] - num, 0)] += 1\n\t\tnum += 1\n\tprint(num)\n", "from sys import stdin, stdout\nt = int(stdin.readline())\nfor i in range(t):\n\t(n, k) = map(int, stdin.readline().split())\n\tvalues = sorted(list(map(int, stdin.readline().split())))\n\tlength = [values[0], n - values[-1] + 1]\n\tfor i in range(0, k - 1):\n\t\tcnt = values[i + 1] - values[i] + 1\n\t\tif cnt & 1:\n\t\t\tlength.append((cnt >> 1) + 1)\n\t\telse:\n\t\t\tlength.append(cnt >> 1)\n\tstdout.write(str(max(length)) + '\\n')\n", "t = int(input())\nfor y in range(t):\n\t(n, k) = [int(x) for x in input().split()]\n\tx = [int(x) for x in input().split()]\n\tlg = x[0]\n\trg = n - x[-1] + 1\n\ttmp = []\n\tfor x1 in range(len(x) - 1):\n\t\ttmp.append((x[x1 + 1] - x[x1]) // 2 + 1)\n\tif len(tmp) == 0:\n\t\ttmp = [0, 0]\n\tprint(max(lg, rg, max(tmp)))\n", "for T in range(int(input())):\n\tX = list(map(int, input().split()))\n\tSegments = [False for i in range(X[0])]\n\tSecond = 0\n\tTaps = list(map(int, input().split()))\n\twhile Segments.count(True) != X[0]:\n\t\tfor Tap in Taps:\n\t\t\tSegments[max(0, Tap - Second - 1)] = True\n\t\t\tSegments[min(X[0] - 1, Tap + Second - 1)] = True\n\t\tSecond += 1\n\tprint(Second)\n", "t = int(input())\nwhile t:\n\tt -= 1\n\ts = input().split()\n\tm = int(s[0])\n\tn = int(s[1])\n\ts = input().split()\n\tfor i in range(n):\n\t\ts[i] = int(s[i])\n\tmtime = s[0]\n\tfor i in range(1, n):\n\t\tif mtime < (s[i] - s[i - 1]) // 2 + 1:\n\t\t\tmtime = (s[i] - s[i - 1]) // 2 + 1\n\tif mtime < m - s[len(s) - 1] + 1:\n\t\tmtime = m - s[len(s) - 1] + 1\n\tprint(mtime)\n", "t = int(input())\nwhile t > 0:\n\t(n, k) = map(int, input().split())\n\ta = []\n\ta = list(map(int, input().split()))\n\tl = 1\n\tr = n\n\tres = 1\n\tfor i in range(k):\n\t\tres = max(res, (a[i] - l) // 2 + 1)\n\t\tl = a[i]\n\tres = max(res, a[0] - 1 + 1)\n\tres = max(res, n - a[k - 1] + 1)\n\tprint(res)\n\tt -= 1\n", "T = int(input())\nfor _ in range(T):\n\t(n, k) = map(int, input().split())\n\tT = list(map(int, input().split()))\n\tl = -1\n\tr = n\n\twhile l < r - 1:\n\t\ti = (l + r) // 2\n\t\tA = [0] * (n + 2)\n\t\tfor t in T:\n\t\t\tA[max(t - i - 1, 0)] += 1\n\t\t\tA[min(t + i, n)] -= 1\n\t\tfor j in range(1, n + 1):\n\t\t\tA[j] += A[j - 1]\n\t\tif n == sum((1 for a in A[:n] if a > 0)):\n\t\t\tr = i\n\t\telse:\n\t\t\tl = i\n\tprint(r + 1)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\td = []\n\tfor i in range(1, len(x)):\n\t\td.append((x[i] - x[i - 1]) // 2 + 1)\n\td.append(x[0])\n\td.append(n - x[-1] + 1)\n\tprint(max(d))\n", "import sys\nimport os\nimport math\nimport re\nt = int(input())\n\ndef fullSet(theset, n):\n\tfor i in range(1, n + 1):\n\t\tif i in theset:\n\t\t\tcontinue\n\t\telse:\n\t\t\treturn False\n\treturn True\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = list(map(int, input().split()))\n\tif n == k:\n\t\tprint('1')\n\telse:\n\t\tcount = 1\n\t\tx = set(taps)\n\t\twhile len(x) < n:\n\t\t\tcount += 1\n\t\t\ti = list((item for item in x))\n\t\t\tfor val in i:\n\t\t\t\tif val - 1 > 0:\n\t\t\t\t\tx.add(val - 1)\n\t\t\t\tif val + 1 <= n:\n\t\t\t\t\tx.add(val + 1)\n\t\tprint(count)\n", "t = int(input())\nfor i in range(t):\n\ttime = 0\n\t(n, k) = map(int, input().split(' '))\n\tx = list(map(int, input().split(' ')))\n\tarr_bed = list(range(1, n + 1))\n\twhile arr_bed != []:\n\t\ttime += 1\n\t\tx_copy = []\n\t\tfor j in x:\n\t\t\tif j in arr_bed:\n\t\t\t\tarr_bed.remove(j)\n\t\t\tif j - 1 > 0:\n\t\t\t\tif j - 1 not in x_copy:\n\t\t\t\t\tx_copy.append(j - 1)\n\t\t\tif j + 1 <= n:\n\t\t\t\tif j + 1 not in x_copy:\n\t\t\t\t\tx_copy.append(j + 1)\n\t\tx = x_copy[:]\n\tprint(time)\n", "t = int(input())\nresultlist = []\nfor m in range(0, t):\n\t(n, k) = map(int, input().split())\n\tnum = input()\n\tklist = list(map(int, num.strip().split()))\n\tfrontSpace = klist[0] - 1\n\tbackSpace = n - int(klist[k - 1])\n\tinnerSpace = 0\n\tinnerSpaceResult = 0\n\tfor j in range(0, k - 1):\n\t\tdec = int(klist[j + 1]) - int(klist[j]) - 1\n\t\tif dec > innerSpace:\n\t\t\tinnerSpace = dec\n\tif innerSpace % 2 == 0:\n\t\tinnerSpaceResult = innerSpace / 2\n\telse:\n\t\tinnerSpaceResult = (innerSpace + 1) / 2\n\tresult = int(max(frontSpace, backSpace, innerSpaceResult) + 1)\n\tresultlist.append(result)\nfor item in resultlist:\n\tprint(item)\n", "t = int(input())\nfor i in range(t):\n\tn = [int(i) for i in input().split()]\n\tmin1 = 0\n\ta = [int(i) for i in input().split()]\n\tinitial = a[0]\n\tfor i in a[1:]:\n\t\tmin1 = max(min1, i - initial)\n\t\tinitial = i\n\tprint(max(min1 // 2, a[0] - 1, n[0] - a[-1]) + 1)\n", "class CodeforcesTask920ASolution:\n\n\tdef __init__(self):\n\t\tself.result = ''\n\t\tself.test_cases = 0\n\n\tdef read_input(self):\n\t\tself.test_cases = int(input())\n\n\tdef process_task(self):\n\t\tfor test in range(self.test_cases):\n\t\t\tn_k = [int(x) for x in input().split(' ')]\n\t\t\ttaps = [int(x) for x in input().split(' ')]\n\t\t\tpositioned_taps = [1 if x + 1 in taps else 0 for x in range(n_k[0])]\n\t\t\tforward_tap = [-1 for x in range(n_k[0])]\n\t\t\tbackward_tap = [-1 for x in range(n_k[0])]\n\t\t\tlast_f = -1\n\t\t\tfor x in range(n_k[0]):\n\t\t\t\tif positioned_taps[x]:\n\t\t\t\t\tlast_f = x\n\t\t\t\tif last_f >= 0:\n\t\t\t\t\tforward_tap[x] = abs(x - last_f) + 1\n\t\t\tlast_b = -1\n\t\t\tfor x in range(n_k[0] - 1, -1, -1):\n\t\t\t\tif positioned_taps[x]:\n\t\t\t\t\tlast_b = x\n\t\t\t\tif last_b >= 0:\n\t\t\t\t\tbackward_tap[x] = abs(x - last_b) + 1\n\t\t\ttapping = [0 for x in range(n_k[0])]\n\t\t\tfor x in range(n_k[0]):\n\t\t\t\tif forward_tap[x] == -1:\n\t\t\t\t\ttapping[x] = backward_tap[x]\n\t\t\t\telif backward_tap[x] == -1:\n\t\t\t\t\ttapping[x] = forward_tap[x]\n\t\t\t\telse:\n\t\t\t\t\ttapping[x] = min(forward_tap[x], backward_tap[x])\n\t\t\tprint(max(tapping))\n\n\tdef get_result(self):\n\t\treturn self.result\nSolution = CodeforcesTask920ASolution()\nSolution.read_input()\nSolution.process_task()\nprint(Solution.get_result())\n", "t = int(input())\nfor i in range(t):\n\ts = input().split()\n\tn = int(s[0])\n\tk = int(s[1])\n\ta = []\n\tz = input().split()\n\tfor d in z:\n\t\ta.append(int(d))\n\tmx = 0\n\tfor x in range(k - 1):\n\t\tif a[x + 1] - a[x] > mx:\n\t\t\tmx = a[x + 1] - a[x] - 1\n\tif mx == 0:\n\t\tprint(1 + max(a[0] - 1, n - a[-1]))\n\telif int(mx / 2 + 0.5) >= max(a[0] - 1, n - a[-1]):\n\t\tprint(1 + int(mx / 2 + 0.5))\n\telse:\n\t\tprint(1 + max(a[0] - 1, n - a[-1]))\n", "t = int(input())\nfor i in range(t):\n\tcount = 1\n\t(n, k) = map(int, input().split())\n\tgarden = [0 for num in range(n)]\n\ta = input().split(' ')\n\tb = [int(x) for x in a]\n\tfor number in b:\n\t\tgarden[number - 1] = 1\n\twhile 0 in garden:\n\t\tsequence = []\n\t\tfor number in range(len(garden)):\n\t\t\tif garden[number] == 1:\n\t\t\t\tsequence.append(number)\n\t\tfor number in sequence:\n\t\t\tif number + 1 < len(garden):\n\t\t\t\tgarden[number + 1] = 1\n\t\t\tif number - 1 >= 0:\n\t\t\t\tgarden[number - 1] = 1\n\t\t\tgarden[number] = 2\n\t\tcount += 1\n\tprint(count)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tans = []\n\tfor j in range(k - 1):\n\t\tans.append((x[j + 1] - x[j]) // 2 + 1)\n\tans.append(x[0])\n\tans.append(n - x[k - 1] + 1)\n\tprint(max(ans))\n", "import sys, math, itertools\nfrom collections import Counter, deque, defaultdict\nfrom bisect import bisect_left, bisect_right\nfrom heapq import heappop, heappush, heapify, nlargest\nfrom copy import deepcopy\nmod = 10 ** 9 + 7\nINF = float('inf')\n\ndef inp():\n\treturn int(sys.stdin.readline())\n\ndef inpl():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef inpl_1():\n\treturn list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))\n\ndef inps():\n\treturn sys.stdin.readline()\n\ndef inpsl(x):\n\ttmp = sys.stdin.readline()\n\treturn list(tmp[:x])\n\ndef err(x):\n\tprint(x)\n\texit()\nfor _ in range(inp()):\n\t(n, k) = inpl()\n\ta = inpl_1()\n\tres = [INF] * n\n\tse = set(a)\n\tpr = -INF\n\tfor i in range(n):\n\t\tif i in se:\n\t\t\tpr = i\n\t\tres[i] = min(res[i], i - pr + 1)\n\tpr = INF\n\tfor i in range(n)[::-1]:\n\t\tif i in se:\n\t\t\tpr = i\n\t\tres[i] = min(res[i], pr - i + 1)\n\tprint(max(res))\n", "t = int(input())\na = [[] for i in range(t)]\nfor i in range(t):\n\ta[i].append([int(x) for x in input().split()])\n\ta[i].append([int(x) for x in input().split()])\nfor i in range(t):\n\tg = [0] * a[i][0][0]\n\tfor j in range(a[i][0][1]):\n\t\tg[a[i][1][j] - 1] = 2\n\tfl = 1\n\twhile g.count(0) != 0:\n\t\tfl += 1\n\t\tfor j in range(len(g)):\n\t\t\tif j > 0 and j + 1 < len(g):\n\t\t\t\tif g[j - 1] == 2 or g[j + 1] == 2:\n\t\t\t\t\tg[j] = 1\n\t\t\telif j > 0:\n\t\t\t\tif g[j - 1] == 2:\n\t\t\t\t\tg[j] = 1\n\t\t\telif g[j + 1] == 2:\n\t\t\t\tg[j] = 1\n\t\tfor j in range(len(g)):\n\t\t\tif g[j] == 1:\n\t\t\t\tg[j] = 2\n\tprint(fl)\n", "t = int(input())\nfor o in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\ta.sort()\n\tans = a[0]\n\tfor i in range(1, k):\n\t\tans = max(ans, (a[i] - a[i - 1] + 2) // 2)\n\tans = max(ans, n - a[k - 1] + 1)\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tarr = list(map(int, input().split()))\n\ts = 1\n\tt = [False] * n\n\tfor i in arr:\n\t\tt[i - 1] = True\n\twhile set(t) != {True}:\n\t\tfor j in arr:\n\t\t\tif j + s <= n:\n\t\t\t\tt[j + s - 1] = True\n\t\t\tif j - s > 0 and j - s <= n:\n\t\t\t\tt[j - s - 1] = True\n\t\ts += 1\n\tprint(s)\n", "t = int(input())\nans = []\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tkran = list(map(int, input().split()))\n\tkran.append(1)\n\tkran.append(n)\n\tkran.sort()\n\tdist = []\n\tdist.append(kran[1] - kran[0] + 1)\n\tdist.append(kran[k + 1] - kran[k] + 1)\n\tfor i in range(2, k + 1):\n\t\tdist.append((kran[i] - kran[i - 1]) // 2 + 1)\n\tdist.sort(reverse=1)\n\tans.append(dist[0])\nfor i in ans:\n\tprint(i)\n", "GI = lambda : int(input())\nGIS = lambda : map(int, input().split())\nLGIS = lambda : list(GIS())\n\ndef main():\n\tfor _ in range(GI()):\n\t\t(n, k) = GIS()\n\t\tl = [0] * n\n\t\tfor x in GIS():\n\t\t\tl[x - 1] = 1\n\t\tlls = ([0] * n, [0] * n)\n\t\tfor dir in lls:\n\t\t\td = 200\n\t\t\tfor x in range(n):\n\t\t\t\tif l[x]:\n\t\t\t\t\td = 0\n\t\t\t\telse:\n\t\t\t\t\td += 1\n\t\t\t\tdir[x] = d\n\t\t\tl.reverse()\n\t\tlls[1].reverse()\n\t\tprint(max(map(min, zip(*lls))) + 1)\nmain()\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tmx = max(x[0], n - x[-1] + 1)\n\tfor i in range(1, k):\n\t\tmx = max(math.floor((x[i] - x[i - 1]) / 2) + 1, mx)\n\tprint(mx)\n", "from math import ceil\nans = list()\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ts = list(map(int, input().split()))\n\tmm = max(s[0], n - s[-1] + 1)\n\tfor j in range(1, k):\n\t\tv = ceil((s[j] - s[j - 1] + 1) / 2)\n\t\tmm = max(v, mm)\n\tans.append(mm)\nfor x in ans:\n\tprint(x)\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\ttime = 1\n\twhile True:\n\t\tused = [False] * n\n\t\tfor xx in x:\n\t\t\tfor i in range(time):\n\t\t\t\tused[max(0, xx - i - 1)] = True\n\t\t\t\tused[min(n - 1, xx + i - 1)] = True\n\t\tif used.count(False) == 0:\n\t\t\tbreak\n\t\ttime += 1\n\tprint(time)\n", "def solve(field, segments):\n\ti = 1\n\twhile True:\n\t\tfor s in segments:\n\t\t\tfield[s[0]] = field[s[1]] = 1\n\t\t\tif s[0] > 0:\n\t\t\t\ts[0] -= 1\n\t\t\tif s[1] < len(field) - 1:\n\t\t\t\ts[1] += 1\n\t\tif sum(field) == len(field):\n\t\t\tprint(i)\n\t\t\treturn\n\t\ti += 1\ntests = int(input())\nwhile tests:\n\ttests -= 1\n\t(n, k) = map(int, input().split())\n\tf = [0 for _ in range(n)]\n\ttreaps = list(map(int, input().split()))\n\tseg = []\n\tfor c in treaps:\n\t\tseg.append([c - 1, c - 1])\n\tsolve(f, seg)\n", "alph = 'abcdefghijklmnopqrstuvwxyz'\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tmax_p = 0\n\tp = list(map(int, input().split()))\n\tp.sort()\n\tfor j in range(k - 1):\n\t\tmax_p = max(max_p, p[j + 1] - p[j])\n\tprint(max(p[0], n - p[-1] + 1, 1 + max_p // 2))\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = list(map(int, input().split()))\n\tx = [int(x) - 1 for x in input().split()]\n\tb = [False] * n\n\ttn = 0\n\twhile not all(b):\n\t\ttn += 1\n\t\tfor i in x:\n\t\t\tfor j in range(max(0, i - (tn - 1)), min(i + (tn - 1) + 1, n)):\n\t\t\t\tb[j] = True\n\tprint(tn)\n", "t = int(input())\nans = list()\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tm = x[0]\n\tfor (i, el) in enumerate(x[1:]):\n\t\tm = max(m, (el - x[i]) // 2 + 1)\n\tm = max(m, n - x[-1] + 1)\n\tans.append(m)\nprint('\\n'.join(map(str, ans)))\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = list(map(int, input().split()))\n\tx = list(map(int, input().split()))\n\tb = []\n\tfor i in range(1, n + 1):\n\t\ta = []\n\t\tfor j in range(k):\n\t\t\ta.append(abs(x[j] - i))\n\t\tb.append(min(a))\n\tprint(max(b) + 1)\n", "import math\nt = int(input())\nwhile t > 0:\n\t(size, tap) = map(int, input().split())\n\tdp = [0 for _ in range(tap + 1)]\n\tloc = list(map(int, input().split()))\n\tif tap == 1:\n\t\tprint(max(loc[0], size - loc[0] + 1))\n\telse:\n\t\tdp[1] = loc[0]\n\t\tfor i in range(1, tap):\n\t\t\tdp[i + 1] = int(math.ceil((loc[i] - loc[i - 1] - 1) / 2) + 1)\n\t\tdp[tap] = max(dp[tap], size - loc[tap - 1] + 1)\n\t\tfor j in range(tap - 2, -1):\n\t\t\tdp[j] = max(dp[j], int(math.ceil((loc[j] - loc[j - 1] - 1) / 2) + 1))\n\t\tprint(max(dp))\n\tt -= 1\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\tif len(l) == n:\n\t\tprint(1)\n\telse:\n\t\tdp = [200] * (n + 1)\n\t\tdp[0] = -1\n\t\tfor i in l:\n\t\t\tdp[i] = 1\n\t\tfor i in range(1, n + 1):\n\t\t\tif dp[i] == 1:\n\t\t\t\tcontinue\n\t\t\tfor j in l:\n\t\t\t\tdp[i] = min(abs(i - j), dp[i])\n\t\tprint(max(dp) + 1)\n", "n = int(input())\nfor i in range(n):\n\t(k, m) = map(int, input().split())\n\tc = list(map(int, input().split()))\n\tl = max(k - c[-1] + 1, c[0])\n\tfor j in range(m - 1):\n\t\tl = max(l, (c[j + 1] - c[j]) // 2 + 1)\n\tprint(l)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport math\nfrom queue import Queue\nimport collections\nimport itertools\nimport bisect\nimport heapq\nimport random\n\ndef main():\n\tpass\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef binary(n):\n\treturn bin(n).replace('0b', '')\n\ndef decimal(s):\n\treturn int(s, 2)\n\ndef pow2(n):\n\tp = 0\n\twhile n > 1:\n\t\tn //= 2\n\t\tp += 1\n\treturn p\n\ndef primeFactors(n):\n\tl = []\n\twhile n % 2 == 0:\n\t\tl.append(2)\n\t\tn = n / 2\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tl.append(i)\n\t\t\tn = n / i\n\tif n > 2:\n\t\tl.append(int(n))\n\treturn l\n\ndef primeFactorsCount(n):\n\tcnt = 0\n\twhile n % 2 == 0:\n\t\tcnt += 1\n\t\tn = n // 2\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tcnt += 1\n\t\t\tn = n // i\n\tif n > 2:\n\t\tcnt += 1\n\treturn cnt\n\ndef isPrime(n):\n\tif n == 1:\n\t\treturn False\n\telse:\n\t\troot = int(n ** 0.5)\n\t\troot += 1\n\t\tfor i in range(2, root):\n\t\t\tif n % i == 0:\n\t\t\t\treturn False\n\t\treturn True\n\ndef maxPrimeFactors(n):\n\tmaxPrime = -1\n\twhile n % 2 == 0:\n\t\tmaxPrime = 2\n\t\tn >>= 1\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tmaxPrime = i\n\t\t\tn = n / i\n\tif n > 2:\n\t\tmaxPrime = n\n\treturn int(maxPrime)\n\ndef countcon(s, i):\n\tc = 0\n\tch = s[i]\n\tfor i in range(i, len(s)):\n\t\tif s[i] == ch:\n\t\t\tc += 1\n\t\telse:\n\t\t\tbreak\n\treturn c\n\ndef lis(arr):\n\tn = len(arr)\n\tlis = [1] * n\n\tfor i in range(1, n):\n\t\tfor j in range(0, i):\n\t\t\tif arr[i] > arr[j] and lis[i] < lis[j] + 1:\n\t\t\t\tlis[i] = lis[j] + 1\n\tmaximum = 0\n\tfor i in range(n):\n\t\tmaximum = max(maximum, lis[i])\n\treturn maximum\n\ndef isSubSequence(str1, str2):\n\tm = len(str1)\n\tn = len(str2)\n\tj = 0\n\ti = 0\n\twhile j < m and i < n:\n\t\tif str1[j] == str2[i]:\n\t\t\tj = j + 1\n\t\ti = i + 1\n\treturn j == m\n\ndef maxfac(n):\n\troot = int(n ** 0.5)\n\tfor i in range(2, root + 1):\n\t\tif n % i == 0:\n\t\t\treturn n // i\n\treturn n\n\ndef p2(n):\n\tc = 0\n\twhile n % 2 == 0:\n\t\tn //= 2\n\t\tc += 1\n\treturn c\n\ndef seive(n):\n\tprimes = [True] * (n + 1)\n\tprimes[1] = primes[0] = False\n\ti = 2\n\twhile i * i <= n:\n\t\tif primes[i] == True:\n\t\t\tfor j in range(i * i, n + 1, i):\n\t\t\t\tprimes[j] = False\n\t\ti += 1\n\tpr = []\n\tfor i in range(0, n + 1):\n\t\tif primes[i]:\n\t\t\tpr.append(i)\n\treturn pr\n\ndef ncr(n, r, p):\n\tnum = den = 1\n\tfor i in range(r):\n\t\tnum = num * (n - i) % p\n\t\tden = den * (i + 1) % p\n\treturn num * pow(den, p - 2, p) % p\n\ndef denofactinverse(n, m):\n\tfac = 1\n\tfor i in range(1, n + 1):\n\t\tfac = fac * i % m\n\treturn pow(fac, m - 2, m)\n\ndef numofact(n, m):\n\tfac = 1\n\tfor i in range(1, n + 1):\n\t\tfac = fac * i % m\n\treturn fac\n\ndef sod(n):\n\ts = 0\n\twhile n > 0:\n\t\ts += n % 10\n\t\tn //= 10\n\treturn s\n\ndef getXor(n):\n\txor = 1\n\tfor i in range(2, n + 1):\n\t\txor = xor ^ i\n\treturn xor\nfor xyz in range(0, int(input())):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\tt = [0] * n\n\tfor i in l:\n\t\tt[i - 1] = 1\n\tans = 1\n\tfilled = len(l)\n\twhile filled < n:\n\t\tans += 1\n\t\tnew = []\n\t\tfor i in range(0, n):\n\t\t\tif t[i]:\n\t\t\t\tif t[max(0, i - 1)] == 0:\n\t\t\t\t\tnew.append(max(0, i - 1))\n\t\t\t\tif t[min(n - 1, i + 1)] == 0:\n\t\t\t\t\tnew.append(min(n - 1, i + 1))\n\t\tfor i in new:\n\t\t\tif t[i]:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tfilled += 1\n\t\t\t\tt[i] = 1\n\tprint(ans)\n", "def getinput():\n\treturn [int(x) for x in input().strip().split()]\nt = int(input())\nfor t1 in range(t):\n\t(n, k) = getinput()\n\tarr = getinput()\n\tans = max(arr[0], n - arr[-1] + 1)\n\tfor i in range(1, k):\n\t\tans = max(ans, (arr[i] - arr[i - 1] + 2) // 2)\n\tprint(ans)\n", "t = int(input())\nINF = 548\nfor z in range(t):\n\t(n, k) = map(int, input().split())\n\ta = [INF] * n\n\tc = [int(x) for x in input().split()]\n\tfor i in c:\n\t\ta[i - 1] = 0\n\tlast = -INF\n\tfor i in range(n):\n\t\tif a[i] == 0:\n\t\t\tlast = i\n\t\telse:\n\t\t\ta[i] = min(a[i], i - last)\n\tlast = INF\n\tfor i in range(n - 1, -1, -1):\n\t\tif a[i] == 0:\n\t\t\tlast = i\n\t\telse:\n\t\t\ta[i] = min(a[i], last - i)\n\tprint(max(a) + 1)\n", "import getpass\nimport sys\nimport math\n\ndef ria():\n\treturn [int(i) for i in input().split()]\nfiles = True\nif getpass.getuser() == 'frohenk' and files:\n\tsys.stdin = open('test.in')\nt = ria()[0]\nfor kekas in range(t):\n\t(n, k) = ria()\n\tar = ria()\n\tmaxi = max(ar[0], n - ar[len(ar) - 1] + 1)\n\tfor j in range(1, k):\n\t\tmaxi = max(maxi, 1 + math.floor((ar[j] - ar[j - 1]) / 2))\n\tprint(maxi)\n", "import sys, bisect\ntc = int(sys.stdin.readline())\nfor _ in range(tc):\n\t(n, m) = map(int, sys.stdin.readline().split())\n\tarr = list(map(int, sys.stdin.readline().split()))\n\tdp = [9876543210] * (n + 1)\n\tfor i in arr:\n\t\tfor j in range(1, n + 1):\n\t\t\tdp[j] = min(dp[j], abs(i - j))\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\tans = max(ans, dp[i])\n\tprint(ans + 1)\n", "t = int(input())\nfor i in range(t):\n\tarr = list((int(x) for x in input().split(' ')))\n\tn = arr[0]\n\tk = arr[1]\n\ta = list((int(x) - 1 for x in input().split(' ')))\n\tans = list((5000 for _ in range(n)))\n\tfor x in a:\n\t\tcount = 1\n\t\tfor j in range(x, n, 1):\n\t\t\tans[j] = min(count, ans[j])\n\t\t\tcount += 1\n\t\tcount = 1\n\t\tfor j in range(x, -1, -1):\n\t\t\tans[j] = min(count, ans[j])\n\t\t\tcount += 1\n\tres = max(ans)\n\tprint(res)\n", "def max_dist(N, taps):\n\tm = max(taps[0], N - 1 - taps[-1])\n\tfor (lo, hi) in zip(taps, taps[1:]):\n\t\tm = max((hi - lo) // 2, m)\n\treturn m\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(N, K) = map(int, input().split())\n\t\ttaps = [int(x) - 1 for x in input().split()]\n\t\tprint(1 + max_dist(N, taps))\nmain()\n", "import sys\n\ndef main():\n\tT = int(input())\n\tfor _ in range(T):\n\t\t(n, k) = map(int, input().split())\n\t\ttaps = list(map(int, input().split()))\n\t\tfor t in range(n + n):\n\t\t\twatered = [0] * n\n\t\t\tfor tap in taps:\n\t\t\t\t(l, r) = (max(0, tap - 1 - t), min(n, tap + t))\n\t\t\t\twatered[l:r] = [1] * (r - l)\n\t\t\tif sum(watered) == n:\n\t\t\t\tprint(t + 1)\n\t\t\t\tbreak\nmain()\n", "t = int(input())\nfor e in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = list(map(int, input().split()))\n\ttime = taps[0]\n\tfor i in range(k - 1):\n\t\ttime = max(time, 1 + (taps[i + 1] - taps[i]) // 2)\n\ttime = max(time, n - taps[-1] + 1)\n\tprint(time)\n", "t = int(input())\nfor x in range(t):\n\t(n, k) = map(int, input().split())\n\tlst = []\n\tfor y in input().split():\n\t\tlst.append(int(y))\n\tl = max(lst[0], n + 1 - lst[-1])\n\tfor y in range(1, len(lst)):\n\t\tl = max(l, (lst[y] - lst[y - 1] + 2) // 2)\n\tprint(l)\n", "def fn(n, array):\n\tarray_n = [x for x in range(1, n + 1)]\n\tarray_space = list(set(array_n).difference(set(array)))\n\tmax_gap = []\n\tfor space in array_space:\n\t\tmin_gap = []\n\t\tfor tap in array:\n\t\t\tmin_gap.append(abs(tap - space))\n\t\tmax_gap.append(min(min_gap))\n\tif max_gap == []:\n\t\treturn 1\n\telse:\n\t\treturn max(max_gap) + 1\nn = int(input())\nsamples = []\nfor _ in range(n * 2):\n\ttry:\n\t\tline = input()\n\texcept EOFError:\n\t\tbreak\n\tsamples.append([int(x) for x in line.split()])\nfor i in range(1, n + 1):\n\tres = fn(samples[2 * (i - 1)][0], samples[i * 2 - 1])\n\tprint(res)\n", "import math\nt = int(input())\nx = []\nans = []\nfor i in range(t):\n\t(n, k) = input().split()\n\tn = int(n)\n\tk = int(k)\n\tm = 0\n\tx = input().split()\n\tfor j in range(len(x)):\n\t\tx[j] = int(x[j])\n\t\tif j > 0:\n\t\t\tm = max((x[j] - x[j - 1]) // 2 + 1, m)\n\tm = max(m, n - x[k - 1] + 1)\n\tm = max(m, x[0])\n\tx = []\n\tans.append(m)\nfor i in range(len(ans)):\n\tprint(ans[i])\n", "def max_num(n, k, list_sl):\n\tnum_left = list_sl[0] - 1 + 1\n\tnum_right = n - list_sl[-1] + 1\n\tnum_mid = 0\n\tif k > 1:\n\t\tnum_mid = max([list_sl[i + 1] - list_sl[i] for i in range(k - 1)]) // 2 + 1\n\tresult = max(num_left, num_right, num_mid)\n\treturn result\nt = int(input())\nlist_result = []\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tlist_data = list(map(int, input().split()))\n\tlist_result.append(max_num(n, k, list_data))\nfor time in list_result:\n\tprint(time)\n", "t = int(input())\nit = []\nfor i in range(t):\n\tq = 0\n\ttime = 0\n\tm = []\n\t(n, k) = map(int, input().split())\n\tmas = list(map(int, input().split()))\n\twhile q != n:\n\t\tfor p in mas:\n\t\t\tif p + time < n + 1:\n\t\t\t\tif not p + time in m:\n\t\t\t\t\tq += 1\n\t\t\t\t\tm.append(p + time)\n\t\t\t\tif p - time > 0 and time != 0:\n\t\t\t\t\tif not p - time in m:\n\t\t\t\t\t\tq += 1\n\t\t\t\t\t\tm.append(p - time)\n\t\t\telif p - time > 0 and time != 0:\n\t\t\t\tif not p - time in m:\n\t\t\t\t\tq += 1\n\t\t\t\t\tm.append(p - time)\n\t\t\telse:\n\t\t\t\tdel mas[p]\n\t\ttime += 1\n\tit.append(str(time))\nprint('\\n'.join(it))\n", "m = input()\nm = int(m)\nfor i in range(m):\n\tline = input()\n\ta_b = [int(n) for n in line.split()]\n\ta = a_b[0]\n\tb = a_b[1]\n\tnum_list = input()\n\tnum_list = [int(n) for n in num_list.split()]\n\tif b == 1:\n\t\tprint(max(num_list[0] - 1, a - num_list[0]) + 1)\n\telse:\n\t\tres = []\n\t\tfor i in range(1, len(num_list)):\n\t\t\tres.append(int((num_list[i] - num_list[i - 1]) / 2))\n\t\tres.append(num_list[0] - 1)\n\t\tres.append(a - num_list[-1])\n\t\tprint(max(res) + 1)\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tarr = list(map(int, input().split()))\n\twater = [0] * n\n\t(ans, j) = (1, 0)\n\tfor i in range(k):\n\t\twater[arr[i] - 1] = 1\n\twhile sum(water) < n:\n\t\tans += 1\n\t\tj += 1\n\t\tfor i in range(k):\n\t\t\tif arr[i] - 1 + j < n:\n\t\t\t\twater[arr[i] - 1 + j] = 1\n\t\t\tif arr[i] - 1 - j >= 0:\n\t\t\t\twater[arr[i] - 1 - j] = 1\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\ta = []\n\ta.append(l[0])\n\tfor j in range(k - 1):\n\t\ta.append((l[j + 1] - l[j]) // 2 + 1)\n\ta.append(n - l[k - 1] + 1)\n\tk = max(a)\n\tprint(k)\n", "num = int(input())\nfor num_ in range(num):\n\ttime = 0\n\targs = input().split(' ')\n\t(land, water) = (int(args[0]), int(args[1]))\n\twater_p = []\n\tfor w_p in input().split(' '):\n\t\twater_p.append(int(w_p))\n\tlands = [0] * land\n\twhile 0 in lands:\n\t\tfor one_p in water_p:\n\t\t\tif one_p - 1 - time in range(0, land):\n\t\t\t\tlands[one_p - 1 - time] = 1\n\t\t\tif one_p - 1 + time in range(0, land):\n\t\t\t\tlands[one_p - 1 + time] = 1\n\t\ttime += 1\n\tprint(time)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tmaxi = 0\n\tp = True\n\tfor j in range(len(a)):\n\t\tif len(a) == 1:\n\t\t\tprint(max(a[j], n - a[j] + 1))\n\t\t\tp = False\n\t\t\tbreak\n\t\tif j == 0:\n\t\t\tx = a[j]\n\t\telif j == len(a) - 1:\n\t\t\tx = max(n - a[j] + 1, (a[j] - a[j - 1]) // 2 + 1)\n\t\telse:\n\t\t\tx = (a[j] - a[j - 1]) // 2 + 1\n\t\tmaxi = max(maxi, x)\n\tif p:\n\t\tprint(maxi)\n", "from math import ceil\nn = int(input())\nfor i in range(n):\n\t(f, a) = list(map(int, input().split()))\n\ttaps = sorted(list(map(int, input().split())))\n\tmax_todo = max(taps[0] - 1, f - taps[-1])\n\tfor t in range(a):\n\t\tif t != a - 1:\n\t\t\tif ceil((taps[t + 1] - taps[t] - 1) / 2) > max_todo:\n\t\t\t\tmax_todo = ceil((taps[t + 1] - taps[t] - 1) / 2)\n\tprint(max_todo + 1)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nimport functools\nfrom operator import itemgetter, attrgetter\nfrom collections import Counter\nY = lambda : list(map(int, input().split()))\nP = lambda : map(int, input().split())\nN = lambda : int(input())\nt = N()\nwhile t > 0:\n\t(n, k) = P()\n\ta = Y()\n\t(mx, s) = (a[0] - 1, a[0])\n\tfor i in range(1, k):\n\t\tmx = max(mx, (a[i] - s) // 2)\n\t\ts = a[i]\n\tmx = max(mx, n - s) + 1\n\tprint('%s' % (mx if not n == k else 1))\n\tt -= 1\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\t(mx, last) = (a[0], 0)\n\tfor i in a:\n\t\tif i == last:\n\t\t\tcontinue\n\t\tmx = max(mx, (i - last + 1) // 2 + ((i - last + 1) % 2 == 1))\n\t\tlast = i\n\tif last != n:\n\t\tmx = max(mx, n - last + 1)\n\tprint(mx)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tbeds = [0 for i in range(n)]\n\tfor x in map(int, input().split()):\n\t\tbeds[x - 1] = 1\n\ts = 1\n\twhile True:\n\t\tif sum(beds) == len(beds):\n\t\t\tbreak\n\t\tbeds_cpy = beds[:]\n\t\tfor i in range(len(beds)):\n\t\t\tif beds[i] == 1:\n\t\t\t\tif i == 0:\n\t\t\t\t\tbeds_cpy[i + 1] = 1\n\t\t\t\telif i == len(beds) - 1:\n\t\t\t\t\tbeds_cpy[i - 1] = 1\n\t\t\t\telse:\n\t\t\t\t\tbeds_cpy[i - 1] = beds_cpy[i + 1] = 1\n\t\tbeds = beds_cpy[:]\n\t\ts += 1\n\tprint(s)\n", "t = int(input())\nans = [0] * 300\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tb = max(a[0], n + 1 - a[k - 1])\n\tm = -1\n\tfor j in range(1, k):\n\t\tm = max(m, a[j] - a[j - 1])\n\tans[i] = max((m + 2) // 2, b)\nfor i in range(t):\n\tprint(ans[i])\n", "from collections import defaultdict\nimport math\nfrom sys import stdin\ncasenumber = int(stdin.readline())\nmydict = defaultdict(list)\noutput = []\nfor n in range(casenumber):\n\tstring1 = stdin.readline().strip().split()\n\tbeds = int(string1[0])\n\ttaps = int(string1[1])\n\tmydict[n + 1].append(beds)\n\tmydict[n + 1].append(taps)\n\tstring2 = stdin.readline().strip().split()\n\tfor i in range(taps):\n\t\tmydict[n + 1].append(int(string2[i]))\nfor i in range(0, casenumber):\n\tmaxvalue = 0\n\tfor j in range(mydict[i + 1][0]):\n\t\tminvalue = 200\n\t\tfor k in range(mydict[i + 1][1]):\n\t\t\td = abs(j + 1 - mydict[i + 1][k + 2])\n\t\t\tif d < minvalue:\n\t\t\t\tminvalue = d\n\t\tif minvalue > maxvalue:\n\t\t\tmaxvalue = minvalue\n\toutput.append(maxvalue + 1)\nfor i in range(casenumber):\n\tprint(output[i])\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = list(map(int, input().split()))\n\tgarden = [0] * n\n\tfor i in range(k):\n\t\tgarden[taps[i] - 1] = 1\n\tcount = k\n\tsec = 1\n\twhile count < n:\n\t\tsec += 1\n\t\tfor i in range(k):\n\t\t\tleft = taps[i] - 1 - (sec - 1)\n\t\t\tright = taps[i] - 1 + (sec - 1)\n\t\t\tif left >= 0 and garden[left] == 0:\n\t\t\t\tcount += 1\n\t\t\t\tgarden[left] = 1\n\t\t\tif right < n and garden[right] == 0:\n\t\t\t\tcount += 1\n\t\t\t\tgarden[right] = 1\n\tprint(sec)\n", "def f(n, k, x):\n\tmax_t = n - x[k - 1]\n\tif max_t < x[0] - 1:\n\t\tmax_t = x[0] - 1\n\tfor i in range(k - 1):\n\t\tt = (x[i + 1] - x[i]) // 2\n\t\tif t > max_t:\n\t\t\tmax_t = t\n\treturn max_t + 1\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tprint(f(n, k, x))\n", "for j in range(int(input())):\n\t(n, k) = [int(f) for f in input().split(' ') if f]\n\td = [int(f) for f in input().split(' ') if f]\n\tpointer = 0\n\tr = 0\n\tfor i in range(1, n + 1):\n\t\twhile pointer + 1 < k and d[pointer + 1] <= i:\n\t\t\tpointer += 1\n\t\tv = 999999999\n\t\tif pointer >= 0:\n\t\t\tv = min(v, abs(i - d[pointer]) + 1)\n\t\tif pointer + 1 < k:\n\t\t\tv = min(v, abs(d[pointer + 1] - i) + 1)\n\t\tr = max(r, v)\n\tprint(r)\n", "n = int(input())\nkol = 0\nmax = 0\nmas = []\notv = []\nfor i in range(n):\n\tkol = 0\n\trange1 = 0\n\tmax = 0\n\ts = input()\n\ta = s[0:s.index(' ')]\n\tb = s[s.index(' ') + 1:s.__len__()]\n\tk = input()\n\tmas = k.split(' ')\n\tfor j in range(mas.__len__()):\n\t\tif kol == 0:\n\t\t\trange1 = int(mas[0]) - kol\n\t\t\tif range1 > max:\n\t\t\t\tmax = range1\n\t\t\tkol = a\n\t\telse:\n\t\t\trange1 = (int(mas[j]) - int(mas[j - 1])) // 2 + 1\n\t\t\tif range1 > max:\n\t\t\t\tmax = range1\n\trange1 = int(a) - int(mas[mas.__len__() - 1])\n\tif range1 + 1 > max:\n\t\tmax = range1 + 1\n\totv.append(max)\nfor p in otv:\n\tprint(p)\n", "def build_lands(a):\n\tlands = []\n\tfor one in range(a):\n\t\tlands.append(0)\n\treturn lands\nnum = int(input())\nfor num_ in range(num):\n\ttime = 0\n\targs = input().split(' ')\n\t(land, water) = (int(args[0]), int(args[1]))\n\twater_p = []\n\tfor w_p in input().split(' '):\n\t\twater_p.append(int(w_p))\n\tlands = build_lands(land)\n\twhile 0 in lands:\n\t\tfor one_p in water_p:\n\t\t\tif one_p - 1 - time in range(0, land):\n\t\t\t\tlands[one_p - 1 - time] = 1\n\t\t\tif one_p - 1 + time in range(0, land):\n\t\t\t\tlands[one_p - 1 + time] = 1\n\t\ttime += 1\n\tprint(time)\n", "read = lambda : map(int, input().split())\nT = int(input())\nans = []\nfor kase in range(T):\n\tr = 0\n\t(n, k) = read()\n\ta = [1] * n\n\tb = list(read())\n\ti = 0\n\twhile sum(a):\n\t\tfor num in b:\n\t\t\tnum = num - 1\n\t\t\tif num >= i:\n\t\t\t\ta[num - i] = 0\n\t\t\tif num < n - i:\n\t\t\t\ta[num + i] = 0\n\t\ti = i + 1\n\t\tr = r + 1\n\tans.append(r)\nfor kase in range(T):\n\tprint(ans[kase])\n", "t = int(input())\nfor tt in range(t):\n\t(n, k) = [int(i) for i in input().split()]\n\ta = [int(i) for i in input().split()]\n\tmax_dist = 0\n\tcurr = 0\n\tfor i in range(1, n + 1):\n\t\tx = i\n\t\tif curr != k - 1 and abs(x - a[curr]) > abs(x - a[curr + 1]):\n\t\t\tcurr += 1\n\t\tif abs(x - a[curr]) > max_dist:\n\t\t\tmax_dist = abs(x - a[curr])\n\tprint(max_dist + 1)\n", "I = lambda : map(int, input().split())\nfor _ in range(int(input())):\n\t(n, k) = I()\n\tX = list(I())\n\tprint(1 + max(X[0] - 1, n - X[-1], max((X[i + 1] - X[i] for i in range(k - 1)), default=0) // 2))\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\tma = x[0]\n\tfor j in range(k - 1):\n\t\tl = (x[j + 1] - x[j]) // 2 + 1\n\t\tif ma < l:\n\t\t\tma = l\n\td = n - x[-1] + 1\n\tif ma < d:\n\t\tma = d\n\tprint(ma)\n", "def solve():\n\t(n, k) = [int(x) for x in input().split(' ')]\n\ta = [int(x) for x in input().split(' ')]\n\tm = max(a[0], n - a[-1] + 1)\n\tfor i in range(1, k):\n\t\tg = a[i] - a[i - 1]\n\t\tm = max(m, g // 2 + 1)\n\treturn m\nt = int(input())\nfor case in range(t):\n\tprint(solve())\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().strip().split())\n\tlist = [i for i in map(int, input().strip().split())]\n\tres = 0\n\tif len(list) == 1:\n\t\tres = n - list[0] + 1 if list[0] < n - list[0] + 1 else list[0]\n\t\tprint(res)\n\telse:\n\t\tfor j in range(len(list) - 1):\n\t\t\tif res < list[j + 1] - list[j]:\n\t\t\t\tres = list[j + 1] - list[j]\n\t\tif res % 2 == 1:\n\t\t\tres -= 1\n\t\ttmp = int(res / 2 + 1)\n\t\ttmpdist = list[0] if list[0] > n - list[-1] + 1 else n - list[-1] + 1\n\t\tif tmpdist < tmp:\n\t\t\tprint(tmp)\n\t\telse:\n\t\t\tprint(tmpdist)\n", "T = int(input())\nfor _ in range(T):\n\t(n, k) = list(map(int, input().split()))\n\tc = list(map(int, input().split()))\n\ta = []\n\tfor i in c:\n\t\ta.append(i - 1)\n\tb = [-1] * n\n\tfor i in range(n):\n\t\tm = 300\n\t\tfor j in a:\n\t\t\tm = min(abs(i - j) + 1, m)\n\t\tb[i] = m\n\tprint(max(b))\n", "for _ in range(int(input())):\n\t(n, k) = list(map(int, input().split()))\n\tak = list(map(int, input().split()))\n\tanswer = max(ak[0] - 1, n - ak[-1]) + 1\n\tif k == 1:\n\t\tanswer1 = 1 + max(ak[0] - 1, n - ak[0])\n\telse:\n\t\tanswer1 = max([(ak[i + 1] - ak[i]) // 2 + 1 for i in range(k - 1)])\n\tprint(max(answer, answer1))\n", "t = int(input())\nfor _ in range(t):\n\t(n, m) = input().split()\n\tn = int(n)\n\tm = int(m)\n\ta = [0] * n\n\tfilled = 0\n\tk = 0\n\tr = list(map(int, input().split()))\n\twhile filled == 0:\n\t\tfor i in r:\n\t\t\tif i - 1 + k < n:\n\t\t\t\ta[i - 1 + k] = 1\n\t\t\tif i - 1 - k >= 0:\n\t\t\t\ta[i - 1 - k] = 1\n\t\tk += 1\n\t\tif 0 in a:\n\t\t\tfilled = 0\n\t\telse:\n\t\t\tfilled = 1\n\tprint(k)\n", "def getDistance(NumberOfGarden, NumberOfTap, TapLocation):\n\tdistance = []\n\tdistance.append(TapLocation[0])\n\tdistance.append(NumberOfGarden - TapLocation[len(TapLocation) - 1] + 1)\n\tfor x in range(0, NumberOfTap - 1):\n\t\tdistance.append((TapLocation[x + 1] - TapLocation[x]) // 2 + 1)\n\treturn max(distance)\nn = eval(input())\nresults = []\nfor i in range(0, n):\n\t(NumberOfGarden, NumberOfTap) = map(eval, input().split(' '))\n\tTapLocation = list(map(eval, input().split(' ')))\n\tresults.append(getDistance(NumberOfGarden, NumberOfTap, TapLocation))\nfor result in results:\n\tprint(result)\n", "reps = int(input())\nfor _ in range(reps):\n\t(n, k) = list(map(int, input().split()))\n\ttaps = list(map(int, input().split()))\n\tdtaps = [taps[0]]\n\tfor i in range(1, len(taps)):\n\t\tdtaps.append(int((taps[i] - taps[i - 1]) / 2 + 1))\n\tdtaps.append(n - taps[-1] + 1)\n\tprint(max(dtaps))\n", "def input_data():\n\tt = int(input())\n\tAll_N_list = []\n\tAll_X = []\n\tfor i in range(t):\n\t\t(N, K) = map(int, input().split())\n\t\tX = [int(i) - 1 for i in input().split()]\n\t\tN_list = []\n\t\tfor n in range(N):\n\t\t\tif n in X:\n\t\t\t\tN_list.append(1)\n\t\t\telse:\n\t\t\t\tN_list.append(-1)\n\t\tAll_N_list.append(N_list)\n\t\tAll_X.append(X)\n\treturn (All_N_list, All_X)\n\ndef calcu_time(All_N_list, All_X):\n\tfor i in range(len(All_N_list)):\n\t\ttime = 0\n\t\tfor k in range(len(All_N_list[i]) + 1):\n\t\t\tif -1 not in All_N_list[i] and 1 not in All_N_list[i]:\n\t\t\t\tprint(time)\n\t\t\t\tbreak\n\t\t\tfor xi in All_X[i]:\n\t\t\t\tif xi + k < len(All_N_list[i]):\n\t\t\t\t\tAll_N_list[i][xi + k] = 0\n\t\t\t\tif xi - k > -1:\n\t\t\t\t\tAll_N_list[i][xi - k] = 0\n\t\t\ttime += 1\n(All_N_list, All_X) = input_data()\ncalcu_time(All_N_list, All_X)\n", "import sys, math, os.path\nFILE_INPUT = 'a.in'\nDEBUG = os.path.isfile(FILE_INPUT)\nif DEBUG:\n\tsys.stdin = open(FILE_INPUT)\n\ndef ni():\n\treturn map(int, input().split(' '))\n\ndef nia():\n\treturn list(map(int, input().split()))\n\ndef log(x):\n\tif DEBUG:\n\t\tprint(x)\n(t,) = ni()\nfor _ in range(0, t):\n\t(n, k) = ni()\n\ta = nia()\n\tcount = max(a[0], n - a[-1] + 1)\n\tif k > 1:\n\t\tfor i in range(0, k - 1):\n\t\t\tlog(f'{a[i]} - {a[i + 1]} : {a[i + 1] - a[i]} -> {(a[i + 1] - a[i]) // 2 + 1}')\n\t\t\tcount = max(count, (a[i + 1] - a[i]) // 2 + 1)\n\tprint(count)\n", "cases = int(input())\nls = []\nfor i in range(cases):\n\t(n, k) = map(int, input().split())\n\ttaps = list(map(int, input().split()))\n\tbegin = taps[0]\n\tend = n - taps[-1] + 1\n\tgaps = []\n\tfor i in range(1, k):\n\t\tgaps.append(taps[i] - taps[i - 1] - 1)\n\tif len(gaps) == 0:\n\t\tls.append(max(begin, end))\n\t\tcontinue\n\tfoo = max(gaps)\n\tls.append(max(begin, end, foo % 2 + foo // 2 + 1))\nfor i in ls:\n\tprint(i)\n", "read = lambda : map(int, input().split())\nT = int(input())\nfor ____ in range(T):\n\tr = 0\n\t(n, k) = read()\n\ta = [1] * n\n\tb = list(read())\n\ti = 0\n\twhile sum(a):\n\t\tfor _ in b:\n\t\t\t_ -= 1\n\t\t\tif _ - i >= 0:\n\t\t\t\ta[_ - i] = 0\n\t\t\tif _ + i < n:\n\t\t\t\ta[_ + i] = 0\n\t\ti += 1\n\t\tr += 1\n\tprint(r)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tK = list(map(int, input().split()))\n\tLenght = []\n\tLenght.append(K[0])\n\tfor j in range(1, k):\n\t\tLenght.append(K[j] - K[j - 1] + 1)\n\tLenght.append(n - K[k - 1] + 1)\n\tsec = []\n\tfor m in range(len(Lenght)):\n\t\tif m == 0 or m == len(Lenght) - 1:\n\t\t\tsec.append(Lenght[m])\n\t\telse:\n\t\t\tsec.append((Lenght[m] + 1) // 2)\n\tans = max(sec)\n\tprint(ans)\n", "INF = 99999999\nt = int(input())\nwhile t > 0:\n\tt -= 1\n\t(n, k) = [int(i) for i in input().split()]\n\txi = [int(i) - 1 for i in input().split()]\n\tplace = [INF for i in range(n)]\n\tfor i in xi:\n\t\tfor j in range(n):\n\t\t\tplace[j] = min(place[j], abs(i - j) + 1)\n\tprint(max(place))\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = [int(s) for s in input().split()]\n\tarray = [int(s) for s in input().split()]\n\tif len(array) == 1:\n\t\tprint(max(abs(array[0]), abs(n - array[0] + 1)))\n\t\tcontinue\n\tmax_ = -1\n\tfor i in range(1, len(array)):\n\t\tif array[i] - array[i - 1] + 1 > max_:\n\t\t\tmax_ = array[i] - array[i - 1] + 1\n\tans = math.ceil(max_ / 2)\n\tsec = max(abs(array[0]), abs(n - array[-1] + 1))\n\tprint(max(sec, ans))\n", "t = int(input())\nfor i in range(t):\n\t(n, m) = map(int, input().split())\n\ta = set(map(int, input().split()))\n\tans = [100000 for i in range(n)]\n\tl = -1\n\tfor i in range(n):\n\t\tif i + 1 in a:\n\t\t\tl = 0\n\t\tif l != -1:\n\t\t\tl += 1\n\t\tif l != -1:\n\t\t\tans[i] = min(ans[i], l)\n\tl = -1\n\tfor i in range(n - 1, -1, -1):\n\t\tif i + 1 in a:\n\t\t\tl = 0\n\t\tif l != -1:\n\t\t\tl += 1\n\t\tif l != -1:\n\t\t\tans[i] = min(ans[i], l)\n\tprint(max(ans))\n", "t = int(input().strip())\nfrom math import inf\nfor _ in range(t):\n\t(n, k) = map(int, input().strip().split())\n\txis = list(map(int, input().strip().split()))\n\tsetxis = set(xis)\n\n\tdef find_left_dist(n, s):\n\t\tprev = inf\n\t\tdists = []\n\t\tfor i in range(n):\n\t\t\tif i + 1 in s:\n\t\t\t\tprev = 0\n\t\t\tprev += 1\n\t\t\tdist = prev\n\t\t\tdists.append(dist)\n\t\treturn dists\n\tleftdists = find_left_dist(n, setxis)\n\trevset = {n - i + 1 for i in setxis}\n\trightdists = find_left_dist(n, revset)[::-1]\n\tmindists = [min(r, el) for (r, el) in zip(rightdists, leftdists)]\n\tprint(max(mindists))\n", "def main():\n\t(n, k) = map(int, input().split())\n\tres = [float('inf') for _ in range(n)]\n\tsprinklers = list(map(lambda x: int(x) - 1, input().split()))\n\tfor i in range(n):\n\t\tfor j in sprinklers:\n\t\t\tres[i] = min(res[i], abs(j - i))\n\tprint(1 + max(res))\nT = int(input())\nfor _ in range(T):\n\tmain()\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = input().split(' ')\n\tn = int(n)\n\tk = int(k)\n\tst1 = input().split(' ')\n\tlast = int(st1[0])\n\tdistance = last\n\tfor j in range(k - 1):\n\t\ttmp = int(st1[j + 1])\n\t\tdistance = max(distance, (tmp - last) // 2 + 1)\n\t\tlast = tmp\n\tdistance = max(distance, n - last + 1)\n\tprint(distance)\n", "t = int(input())\ncount = 0\nwhile count < t:\n\tnk = input().split(' ')\n\tn = int(nk[0])\n\tk = int(nk[1])\n\tx = input().split(' ')\n\ti = 0\n\tans = 1\n\tlast = 0\n\twhile i < k:\n\t\txi = int(x[i])\n\t\ttemp = 0\n\t\tif last == 0:\n\t\t\ttemp = xi\n\t\telse:\n\t\t\tdis = xi - last - 1\n\t\t\ttemp = dis // 2 + (0 if dis % 2 == 0 else 1) + 1\n\t\tans = temp if temp > ans else ans\n\t\tlast = xi\n\t\ti += 1\n\tlastD = n - last + 1\n\tans = lastD if lastD > ans else ans\n\tprint(ans)\n\tcount += 1\n", "(t, otv) = (int(input()), list())\nfor i in range(t):\n\t(n, k) = map(int, input().split(' '))\n\tkr = list(map(int, input().split(' ')))\n\ts = '*' * n\n\tfor x in kr:\n\t\ts = s[:x - 1] + '/' + s[x:]\n\tg = list(map(lambda x1: len(x1), s.split('/')))\n\tfor x in range(1, len(g) - 1):\n\t\tg[x] = g[x] // 2 + g[x] % 2\n\totv.append(max(g) + 1)\nfor i in otv:\n\tprint(i)\n", "import sys\ninput = sys.stdin.readline\nfrom math import ceil\nfor i in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ta = sorted(list(map(int, input().split())))\n\tres = 0\n\tind = 0\n\tfor j in range(k):\n\t\tif ind == 0:\n\t\t\tres = max(res, a[j])\n\t\t\tind = a[j]\n\t\telse:\n\t\t\tres = max(res, ceil((a[j] - ind - 1) / 2) + 1)\n\t\t\tind = a[j]\n\tres = max(res, n - ind + 1)\n\tprint(res)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tpk = list(map(int, input().split()))\n\tmintime = 1\n\tfor j in range(k):\n\t\tif j == 0:\n\t\t\tif pk[j] > mintime:\n\t\t\t\tmintime = pk[j]\n\t\tif j == k - 1:\n\t\t\tif n - pk[j] + 1 > mintime:\n\t\t\t\tmintime = n - pk[j] + 1\n\t\tif j > 0:\n\t\t\tcurr = pk[j] - pk[j - 1] - 1\n\t\t\tif (curr + curr % 2) // 2 + 1 > mintime:\n\t\t\t\tmintime = (curr + curr % 2) // 2 + 1\n\tprint(mintime)\n", "for _ in range(int(input().strip())):\n\t(n, k) = map(int, input().split())\n\tl = [int(x) for x in input().split()]\n\tl.sort()\n\tans = max(l[0], n - l[-1] + 1)\n\tfor i in range(1, k):\n\t\tans = max((l[i] - l[i - 1]) // 2 + 1, ans)\n\tprint(ans)\n", "def main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(n, k) = [int(x) for x in input().split()]\n\t\tx = [int(x) for x in input().split()]\n\t\tmm = x[0] - 1 + 1\n\t\tfor i in range(1, k):\n\t\t\tmm = max(mm, 1 + (x[i] - x[i - 1]) // 2)\n\t\tmm = max(mm, n - x[-1] + 1)\n\t\tprint(mm)\nmain()\n", "lul = 0\n\ndef go(v, n):\n\tvv = list(v)\n\tfor i in range(n):\n\t\tvv[i] = v[i]\n\t\tif i < n - 1 and v[i + 1] == 1:\n\t\t\tvv[i] = 1\n\t\tif i > 0 and v[i - 1] == 1:\n\t\t\tvv[i] = 1\n\treturn vv\n\ndef check(v, n):\n\tok = 1\n\tfor i in range(n):\n\t\tif v[i] == 0:\n\t\t\tok = 0\n\treturn ok\n\ndef main():\n\tt = int(input())\n\twhile t > 0:\n\t\tt -= 1\n\t\t(n, k) = map(int, input().split())\n\t\tv = [0] * n\n\t\tans = 1\n\t\tfor i in input().split():\n\t\t\tv[int(i) - 1] = 1\n\t\twhile check(v, n) == 0:\n\t\t\taux = go(v, n)\n\t\t\tv = list(aux)\n\t\t\tans += 1\n\t\tprint(ans)\nmain()\n", "t = int(input())\nfor tt in range(t):\n\t(n, k) = map(int, input().split())\n\tl = list(map(int, input().split()))\n\tl.sort()\n\tres = l[0]\n\tfor i in range(1, len(l)):\n\t\tres = max(res, (l[i] - l[i - 1]) // 2 + 1)\n\tres = max(res, n - l[-1] + 1)\n\tprint(res)\n", "task_number = int(input())\n\ndef is_valid_index(number):\n\treturn 0 <= number < n\nfor i in range(task_number):\n\t(n, k) = list(map(lambda x: int(x), input().split(' ')))\n\tk -= 1\n\tkrans = list(map(lambda x: int(x), input().split()))\n\twatered = [False] * n\n\twatered_number = 0\n\tsec_number = 0\n\twhile watered_number != n:\n\t\tsec_number += 1\n\t\tfor kran in krans:\n\t\t\tkran_n = kran - 1\n\t\t\tfirst = kran_n - (sec_number - 1)\n\t\t\tif is_valid_index(first) and (not watered[first]):\n\t\t\t\twatered[first] = True\n\t\t\t\twatered_number += 1\n\t\t\tsecond = kran_n + (sec_number - 1)\n\t\t\tif is_valid_index(second) and (not watered[second]):\n\t\t\t\twatered[second] = True\n\t\t\t\twatered_number += 1\n\tprint(sec_number)\n", "def dst(a, b):\n\treturn abs(a - b) + 1\n\ndef sol():\n\t(n, k) = map(int, input().split())\n\tarr = list(map(int, input().split()))\n\tans = max(dst(1, arr[0]), dst(n, arr[-1]))\n\tfor i in range(1, k):\n\t\tmed = (arr[i - 1] + arr[i]) // 2\n\t\tans = max(ans, min(dst(arr[i - 1], med), dst(arr[i], med)))\n\tprint(ans)\nt = int(input())\nfor i in range(t):\n\tsol()\n", "import math\nt = int(input())\nfrom time import time\nstart_time = time()\nfor i in range(t):\n\t(n, k) = tuple(map(lambda x: int(x), input().split()))\n\txes = tuple(map(lambda x: int(x), input().split()))\n\tmas = []\n\tfor j in range(len(xes)):\n\t\tif j == 0:\n\t\t\tmas.append(xes[j] - 1)\n\t\t\tcontinue\n\t\tmas.append(math.ceil((xes[j] - xes[j - 1] - 1) / 2))\n\tmas.append(n - xes[-1])\n\tans = 1 + max(mas)\n\tprint(ans)\n", "import os\nfrom io import BytesIO, IOBase\nimport sys\n\ndef main():\n\tfor _ in range(int(input())):\n\t\t(n, k) = map(int, input().split())\n\t\ta = list(map(int, input().split()))\n\t\tans = 0\n\t\tfor i in range(1, n + 1):\n\t\t\tt = n + 1\n\t\t\tfor x in a:\n\t\t\t\tt = min(t, abs(x - i) + 1)\n\t\t\tans = max(ans, t)\n\t\tprint(ans)\n\treturn\nBUFSIZE = 1048576\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\n\ndef input():\n\treturn sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tm = a[0]\n\tfor j in range(k - 1):\n\t\tz = 1 + math.ceil((a[j + 1] - a[j] - 1) / 2)\n\t\tif m < z:\n\t\t\tm = z\n\tif m < n - a[k - 1] + 1:\n\t\tm = n - a[k - 1] + 1\n\tprint(m)\n", "import math\nt = int(input())\nfor k in range(t):\n\t(n, m) = [int(i) for i in input().split()]\n\ta = [int(i) for i in input().split()]\n\ta.append(n + 1)\n\ta.insert(0, 0)\n\tma = 0\n\tfor i in range(1, len(a) - 1):\n\t\tif m == 1:\n\t\t\tma = max(ma, max(a[i] - a[i - 1] - 1, a[i + 1] - a[i] - 1) + 1)\n\t\telif i == 1:\n\t\t\tma = max(ma, max(a[i] - a[i - 1] - 1, (a[i + 1] - a[i] - 1) // 2) + 1)\n\t\telif i == len(a) - 2:\n\t\t\tma = max(ma, max(int(math.ceil((a[i] - a[i - 1] - 1) / 2)), a[i + 1] - a[i] - 1) + 1)\n\t\telse:\n\t\t\tma = max(ma, max(int(math.ceil((a[i] - a[i - 1] - 1) / 2)), (a[i + 1] - a[i] - 1) // 2) + 1)\n\tprint(ma)\n", "cnt = 0\ntime_list = []\ntc = eval(input())\nwhile cnt < tc:\n\tn_k = input()\n\tl = []\n\tl = n_k.split(' ')\n\tn = int(l[0])\n\tk = int(l[1])\n\ttap_pos = input()\n\ttap_pos_list = tap_pos.split(' ')\n\tarr = []\n\tc = 0\n\tfor i in range(0, n):\n\t\tif c < k and i == int(tap_pos_list[c]) - 1:\n\t\t\tarr.append(1)\n\t\t\tc += 1\n\t\telse:\n\t\t\tarr.append(0)\n\ttime = 1\n\tflag = False\n\twhile flag == False:\n\t\tif time == 1:\n\t\t\tfor i in arr:\n\t\t\t\tif i != 1:\n\t\t\t\t\tflag = False\n\t\t\t\t\tbreak\n\t\t\t\tflag = True\n\t\t\tif flag == True:\n\t\t\t\ttime += 1\n\t\t\t\tbreak\n\t\t\ttime += 1\n\t\telse:\n\t\t\tc = 0\n\t\t\tfor i in range(len(arr)):\n\t\t\t\tif c < k and i == int(tap_pos_list[c]) - 1:\n\t\t\t\t\tif i == 0:\n\t\t\t\t\t\tarr[i + (time - 1)] = 1\n\t\t\t\t\telif i == len(arr) - 1:\n\t\t\t\t\t\tarr[i - (time - 1)] = 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tif i - (time - 1) >= 0:\n\t\t\t\t\t\t\tarr[i - (time - 1)] = 1\n\t\t\t\t\t\tif i + (time - 1) <= len(arr) - 1:\n\t\t\t\t\t\t\tarr[i + (time - 1)] = 1\n\t\t\t\t\tc += 1\n\t\t\tfor i in arr:\n\t\t\t\tif i != 1:\n\t\t\t\t\tflag = False\n\t\t\t\t\tbreak\n\t\t\t\tflag = True\n\t\t\ttime += 1\n\ttime_list.append(time - 1)\n\tcnt += 1\nfor i in time_list:\n\tprint(i)\n", "def solve(n, X):\n\ta = X[0] - 1\n\tb = n - X[-1]\n\tc = max((X[i + 1] - X[i] for i in range(len(X) - 1)), default=0) // 2\n\treturn max(a, b, c) + 1\nT = int(input())\nfor _ in range(T):\n\t(n, k) = map(int, input().split())\n\tX = tuple(map(int, input().split()))\n\tprint(solve(n, X))\n", "try:\n\tmain = list()\n\tnum = int(input())\n\tfor f in range(num):\n\t\ttemp = input().split(' ')\n\t\tfor i in range(len(temp)):\n\t\t\ttemp[i] = int(temp[i])\n\t\tlocs = input().split(' ')\n\t\tfor i in range(len(locs)):\n\t\t\tlocs[i] = int(locs[i])\n\t\tif len(locs) != temp[1]:\n\t\t\tsys.exit()\n\t\tlst = list()\n\t\tmins = int()\n\t\tfor i in range(temp[0]):\n\t\t\tlst.append(i + 1)\n\t\twhile True:\n\t\t\tfor i in locs:\n\t\t\t\tif lst.count(i - mins) != 0:\n\t\t\t\t\tlst.remove(i - mins)\n\t\t\t\tif lst.count(i + mins) != 0:\n\t\t\t\t\tlst.remove(i + mins)\n\t\t\tmins += 1\n\t\t\tif len(lst) == 0:\n\t\t\t\tmain.append(mins)\n\t\t\t\tbreak\n\tfor i in main:\n\t\tprint(i)\nexcept:\n\tpass\n", "def my_main():\n\ttest_count = int(input())\n\ttest_cases = []\n\tfor i in range(test_count):\n\t\tsample = []\n\t\tsample.append(input())\n\t\tsample.append(input())\n\t\ttest_cases.append(sample)\n\tfor i in test_cases:\n\t\tgarden_bed = i[0].split()[0]\n\t\ttap_count = i[0].split()[1]\n\t\ttap_list = i[1].split()\n\t\tmaximum = 0\n\t\tif len(tap_list) == 1:\n\t\t\tmaximum = int(tap_list[0]) if int(tap_list[0]) > int(garden_bed) + 1 - int(tap_list[0]) else int(garden_bed) + 1 - int(tap_list[0])\n\t\telse:\n\t\t\tfor i in range(1, len(tap_list)):\n\t\t\t\tif (int(tap_list[i]) - int(tap_list[i - 1])) // 2 + 1 > maximum:\n\t\t\t\t\tmaximum = (int(tap_list[i]) - int(tap_list[i - 1])) // 2 + 1\n\t\t\tif int(garden_bed) + 1 - int(tap_list[-1]) > maximum:\n\t\t\t\tmaximum = int(garden_bed) + 1 - int(tap_list[-1])\n\t\t\tif int(tap_list[0]) > maximum:\n\t\t\t\tmaximum = int(tap_list[0])\n\t\tprint(maximum)\nmy_main()\n", "t = int(input())\nfor _ in range(t):\n\t(n, _) = list(map(int, input().split()))\n\tks = list(map(int, input().split()))\n\ts = set()\n\tc = 0\n\twhile len(s) < n:\n\t\tfor k in ks:\n\t\t\tif k - c > 0:\n\t\t\t\ts.add(k - c)\n\t\t\tif k + c <= n:\n\t\t\t\ts.add(k + c)\n\t\tc += 1\n\tprint(c)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tll = list(map(int, input().split()))\n\tdist = []\n\tfor i in range(k - 1):\n\t\tdist.append(ll[i + 1] - ll[i])\n\tm = 0\n\tif dist != []:\n\t\tm = max(dist)\n\t\tm = m // 2 + 1\n\tf_l = ll[0]\n\tf_r = n - ll[-1] + 1\n\tm = max(m, f_l, f_r)\n\tprint(m)\n", "import sys\nimport math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tmaxi = a[0]\n\tfor j in range(0, k - 1):\n\t\tp = a[j + 1] - a[j] + 1\n\t\tif p % 2 == 1:\n\t\t\tp = p // 2 + 1\n\t\telse:\n\t\t\tp = p // 2\n\t\tmaxi = max(maxi, p)\n\tmaxi = max(maxi, n - a[k - 1] + 1)\n\tprint(maxi)\n", "def get_tmax(n, k, Lk):\n\tt1 = Lk[0]\n\ttk = n - Lk[-1] + 1\n\ttm = 0\n\tfor i in range(len(Lk) - 1):\n\t\tt = Lk[i + 1] - Lk[i] - 1\n\t\tif t % 2:\n\t\t\tt = t // 2 + 2\n\t\telse:\n\t\t\tt = t // 2 + 1\n\t\tif tm < t:\n\t\t\ttm = t\n\treturn max(t1, tk, tm)\nans = []\nntest = int(input())\nfor j in range(ntest):\n\t(n, k) = map(int, input().split())\n\tLk = list(map(int, input().split()))\n\tans.append(get_tmax(n, k, Lk))\nfor i in ans:\n\tprint(i)\n", "t = int(input())\nfor test in range(t):\n\t(n, k) = map(int, input().split())\n\tx = [False for i in range(n)]\n\tfor xi in map(int, input().split()):\n\t\tx[xi - 1] = True\n\t\tn = n - 1\n\ttime = 1\n\twhile n > 0:\n\t\tx2 = x.copy()\n\t\tfor i in range(len(x)):\n\t\t\tif x[i] is True:\n\t\t\t\tif i > 0 and x2[i - 1] is False:\n\t\t\t\t\tx2[i - 1] = True\n\t\t\t\t\tn = n - 1\n\t\t\t\tif i + 1 < len(x) and x2[i + 1] is False:\n\t\t\t\t\tx2[i + 1] = True\n\t\t\t\t\tn = n - 1\n\t\tx = x2.copy()\n\t\ttime = time + 1\n\tprint(time)\n", "import math\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tpositions = list(map(int, input().split()))\n\tans = max(positions[0], n - positions[-1] + 1)\n\tfor j in range(1, k):\n\t\tans = max(ans, math.ceil((positions[j] - positions[j - 1] + 1) / 2))\n\tprint(ans)\n", "for _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tmin_poliv = max(a[0], n - a[-1] + 1)\n\tfor i in range(1, len(a)):\n\t\tif (a[i] - a[i - 1]) // 2 + 1 > min_poliv:\n\t\t\tmin_poliv = (a[i] - a[i - 1]) // 2 + 1\n\tprint(min_poliv)\n", "_ = int(input())\nwhile _ > 0:\n\t(n, m) = map(int, input().split())\n\tA = list(map(int, input().split()))\n\tk = max(A[0], n + 1 - A[-1])\n\tfor i in range(1, m):\n\t\tk = max(k, (A[i] - A[i - 1] + 2) // 2)\n\tprint(k)\n\t_ -= 1\n", "for i in range(int(input())):\n\t(n, k) = [int(x) for x in input().split()]\n\tvalves = [int(x) for x in input().split()]\n\tgr = [False] * n\n\tfor i in valves:\n\t\tgr[i - 1] = True\n\ttime = 1\n\twhile gr.count(True) != n:\n\t\tfor i in valves:\n\t\t\tif i - 1 - time >= 0:\n\t\t\t\tgr[i - 1 - time] = True\n\t\t\tif i - 1 + time < n:\n\t\t\t\tgr[i - 1 + time] = True\n\t\ttime += 1\n\tprint(time)\n", "from collections import deque, defaultdict, Counter\nfrom itertools import product, groupby, permutations, combinations\nfrom math import gcd, floor, inf\nfrom bisect import bisect_right, bisect_left\ncases = int(input())\nfor _ in range(cases):\n\t(k, x) = map(int, input().split())\n\tarr = list(map(int, input().split()))\n\tans = [arr[0], k - arr[-1] + 1]\n\tfor i in range(1, x):\n\t\tans.append((arr[i] - arr[i - 1] + 2) // 2)\n\tprint(max(ans))\n", "R = lambda : map(int, input().split())\nt = int(input())\nans = []\nfor i in range(t):\n\t(n, k) = R()\n\tm = set(R())\n\ts = 1\n\twhile len(m) < n:\n\t\tx = set()\n\t\tx.update(m)\n\t\tfor j in m:\n\t\t\tif j + 1 <= n:\n\t\t\t\tx.add(j + 1)\n\t\t\tif j - 1 >= 1:\n\t\t\t\tx.add(j - 1)\n\t\tm.update(x)\n\t\ts += 1\n\tprint(s)\n", "tc = int(input())\nwhile tc > 0:\n\t(B, T) = map(int, input().split())\n\tA = list(map(int, input().split()))\n\tsec = max(A[0], B + 1 - A[-1])\n\tfor i in range(1, T):\n\t\tsec = max(sec, (A[i] - A[i - 1] + 2) // 2)\n\tprint(sec)\n\ttc -= 1\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ttaps = list(map(int, input().split()))\n\tmaxInterval = taps[0]\n\tfor i in range(len(taps) - 1):\n\t\tmaxInterval = max(maxInterval, (taps[i + 1] - taps[i]) // 2 + 1)\n\tmaxInterval = max(maxInterval, n - taps[-1] + 1)\n\tprint(maxInterval)\n", "t = int(input())\nfor x in range(t):\n\tnk = input()\n\t[n, k] = [int(nk_i) for nk_i in nk.split(' ')]\n\tks_line = input()\n\tks = [int(k_i) - 1 for k_i in ks_line.split(' ')]\n\ta = [0 for ai in range(n)]\n\tr = 0\n\twhile sum(a) < n:\n\t\tr += 1\n\t\tfor i in range(k):\n\t\t\t(l, h) = (ks[i] - r + 1, ks[i] + r - 1)\n\t\t\tfor j in range(l, h + 1):\n\t\t\t\tif 0 <= j < n:\n\t\t\t\t\ta[j] = 1\n\tprint(r)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ts = [int(i) for i in input().split()]\n\ta = max(s[0] - 1, n - s[-1])\n\tfor i in range(k - 1):\n\t\ta = max(a, -(-(s[i + 1] - 1 - s[i]) // 2))\n\tprint(a + 1)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\t(n, k) = list(map(int, input().split()))\n\tarr = sorted(list(map(int, input().split())))\n\tdist = []\n\tother = []\n\tother.append(arr[0] - 1)\n\tfor i in range(1, len(arr)):\n\t\tdist.append(arr[i] - arr[i - 1])\n\tother.append(n - arr[len(arr) - 1])\n\tif dist:\n\t\tprint(max(max(dist) // 2, max(other)) + 1)\n\telse:\n\t\tprint(max(other) + 1)\n", "n = int(input())\n\ndef time(str1, str2):\n\tx = str1[0]\n\tm = [1] * x\n\tl = 0\n\twhile 1:\n\t\tfor k in range(len(str2)):\n\t\t\tif str2[k] - l - 1 >= 0:\n\t\t\t\tm[str2[k] - l - 1] = 0\n\t\t\tif str2[k] + l - 1 <= x - 1:\n\t\t\t\tm[str2[k] + l - 1] = 0\n\t\tl += 1\n\t\tif sum(m) == 0:\n\t\t\treturn l\n\t\t\tbreak\nfor i in range(n):\n\tarr = list(map(int, input().split(' ')))\n\tarr1 = list(map(int, input().split(' ')))\n\tresult = time(arr, arr1)\n\tprint(result)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = [int(v) for v in input().split()]\n\tx = [int(v) - 1 for v in input().split()]\n\tans = 0\n\tcovered = [False] * n\n\twhile not all(covered):\n\t\tfor xi in x:\n\t\t\tfor pos in range(max(0, xi - ans), min(n - 1, xi + ans) + 1):\n\t\t\t\tcovered[pos] = True\n\t\tans += 1\n\tprint(ans)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = (int(p) for p in input().split())\n\ta = list(map(int, input().split()))\n\tif n == 1:\n\t\tprint(1)\n\t\tcontinue\n\tma = 0\n\tfor m in range(len(a) - 1):\n\t\tma = max(ma, a[m + 1] - a[m] + 1)\n\tprint(max(ma // 2 if ma % 2 == 0 else ma // 2 + 1, a[0], n - a[len(a) - 1] + 1))\n", "t = int(input())\nfor y in range(t):\n\t(n, k) = map(int, input().split())\n\ta = [int(j) - 1 for j in input().split()]\n\tans = a[0] + 1\n\tfor i in range(k - 1):\n\t\tans = max((a[i + 1] - a[i] - 1) // 2 + (a[i + 1] - a[i] - 1) % 2 + 1, ans)\n\tans = max(ans, n - a[-1])\n\tprint(ans)\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tpos = list(map(int, input().split()))\n\ti = pos[0]\n\tmax_dist = 0\n\tfor j in pos[1:]:\n\t\tmax_dist = max(max_dist, j - i - 1)\n\t\ti = j\n\tprint(max(max_dist // 2 + max_dist % 2, pos[0] - 1, n - pos[-1]) + 1)\n", "t = int(input())\nfor _ in range(t):\n\t[n, k] = [int(x) for x in input().split()]\n\ta = [int(x) for x in input().split()]\n\tres = max(a[0] - 1, n - a[k - 1])\n\tfor i in range(1, k):\n\t\tres = max(res, (a[i] - a[i - 1]) // 2)\n\tprint(res + 1)\n", "n = int(input())\nfor k in range(n):\n\t(x, y) = map(int, input().split())\n\tt = [0] * (x + 2)\n\tfor i in map(int, input().split()):\n\t\tt[i] = 1\n\tc = 1\n\twhile True:\n\t\tif sum(t[1:x + 1]) == x:\n\t\t\tprint(c)\n\t\t\tbreak\n\t\tk = t[:]\n\t\tfor i in range(1, x + 1):\n\t\t\tif t[i] == 1:\n\t\t\t\tk[i - 1] = k[i + 1] = 1\n\t\tt = k\n\t\tc += 1\n", "t = int(input())\nwhile t > 0:\n\t(n, k) = map(int, input().split())\n\txi = sorted(list(map(int, input().split())))\n\tmaxDist = xi[0]\n\tfor i in range(1, k):\n\t\tmaxDist = max((xi[i] - xi[i - 1] - 1) // 2 + (xi[i] - xi[i - 1] - 1) % 2 + 1, maxDist)\n\tmaxDist = max(maxDist, n + 1 - xi[k - 1])\n\tprint(maxDist)\n\tt -= 1\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = [int(i) for i in input().split()]\n\tx = [int(i) - 1 for i in input().split()]\n\tboundary_maxdiff = max(x[0], n - 1 - x[-1])\n\tmaxdiff = max((x[i + 1] - x[i] for i in range(len(x) - 1))) if len(x) >= 2 else 0\n\tmaxdiff = maxdiff // 2\n\tprint(max(maxdiff, boundary_maxdiff) + 1)\n", "t = int(input())\nans = []\nfor i in range(t):\n\t(n, k) = [int(i) for i in input().split()]\n\tx = [int(i) for i in input().split()]\n\tmax_delta = 0\n\tfor j in range(k - 1):\n\t\tdelta = x[j + 1] - x[j]\n\t\tif delta > max_delta:\n\t\t\tmax_delta = delta\n\tt_ans = max(max_delta // 2 + 1, x[0], n - x[-1] + 1)\n\tans.append(t_ans)\nfor a in ans:\n\tprint(a)\n", "from bisect import *\nfor t in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tK = list(map(int, input().split()))\n\tK.sort()\n\tans = 0\n\tfor i in range(1, n + 1):\n\t\tif i <= K[0]:\n\t\t\tans = max(ans, K[0] - i)\n\t\telif i >= K[-1]:\n\t\t\tans = max(ans, i - K[-1])\n\t\telse:\n\t\t\tpos = bisect_right(K, i)\n\t\t\tans = max(ans, min(K[pos] - i, i - K[pos - 1]))\n\tprint(ans + 1)\n", "t = int(input())\nfor i in range(t):\n\t(n, k) = list(map(int, input().rstrip().split()))\n\ttaps = list(map(int, input().rstrip().split()))\n\ta = [0] * (n + 1)\n\ttime = 1\n\twhile 1:\n\t\tfor i in range(len(taps)):\n\t\t\tif taps[i] - (time - 1) > 0:\n\t\t\t\ta[taps[i] - (time - 1)] = 1\n\t\t\tif taps[i] + (time - 1) <= n:\n\t\t\t\ta[taps[i] + (time - 1)] = 1\n\t\tif a.count(1) == n:\n\t\t\tbreak\n\t\ttime += 1\n\tprint(time)\n", "import sys, math\nt = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tif len(a) == 1:\n\t\tprint(max(a[0] - 1, n - a[0]) + 1)\n\telse:\n\t\tm = 0\n\t\tif a[0] != 1:\n\t\t\tm = max(m, a[0])\n\t\tif a[-1] != n:\n\t\t\tm = max(m, n - a[-1] + 1)\n\t\tfor i in range(1, len(a)):\n\t\t\tm = max(m, math.floor((a[i] - a[i - 1] + 2) / 2))\n\t\tprint(m)\n", "from sys import stdin, stdout\nt = int(stdin.readline())\nfor i in range(t):\n\t(n, k) = map(int, stdin.readline().split())\n\tvalues = list(map(int, stdin.readline().split()))\n\t(l, r) = (0, n)\n\twhile r - l > 1:\n\t\tused = [0 for i in range(n + 1)]\n\t\tm = l + r >> 1\n\t\tfor v in values:\n\t\t\tfor j in range(max(1, v - m + 1), min(n, v + m - 1) + 1):\n\t\t\t\tused[j] = 1\n\t\tif used.count(0) == 1:\n\t\t\tr = m\n\t\telse:\n\t\t\tl = m\n\tstdout.write(str(r) + '\\n')\n", "for _ in range(int(input().strip())):\n\t(n, k) = [int(i) for i in input().strip().split()]\n\tarr = [int(i) for i in input().strip().split()]\n\tfor i in range(len(arr)):\n\t\tarr[i] -= 1\n\tl = [10 ** 10 for i in range(n)]\n\tfor i in arr:\n\t\tfor j in range(len(l)):\n\t\t\tl[j] = min(l[j], abs(j - i) + 1)\n\tprint(max(l))\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\tf = [False for i in range(n)]\n\tc = 0\n\tflag = True\n\tfor x in a:\n\t\tf[x - 1] = True\n\tc += 1\n\tfor x in range(n):\n\t\tif f[x] == False:\n\t\t\tflag = False\n\t\t\tbreak\n\tif flag == True:\n\t\tprint(c)\n\t\tcontinue\n\twhile True:\n\t\tc += 1\n\t\txx = [False for i in range(n)]\n\t\tfor i in range(n):\n\t\t\tif f[i] == True:\n\t\t\t\tif i > 0:\n\t\t\t\t\tf[i - 1] = True\n\t\t\t\tif i + 1 < n and xx[i] == False and (f[i + 1] == False):\n\t\t\t\t\tf[i + 1] = True\n\t\t\t\t\txx[i + 1] = True\n\t\tflag = True\n\t\tfor x in f:\n\t\t\tif x == False:\n\t\t\t\tflag = False\n\t\t\t\tbreak\n\t\tif flag == True:\n\t\t\tbreak\n\tprint(c)\n", "def solution(Nlist):\n\tcount1 = 0\n\tcount2 = 0\n\ti = 0\n\tj = len(Nlist) - 1\n\twhile Nlist[i] == 0:\n\t\tcount1 += 1\n\t\ti += 1\n\twhile Nlist[j] == 0:\n\t\tcount2 += 1\n\t\tj -= 1\n\tcountmid = 0\n\tcountmax = 0\n\tfor k in range(i + 1, j + 1):\n\t\tif Nlist[k] == 0:\n\t\t\tcountmid += 1\n\t\telse:\n\t\t\tcountmax = max(countmax, countmid)\n\t\t\tcountmid = 0\n\treturn max(max(count1, count2), int((countmax + 1) / 2)) + 1\ntestnum = int(input().strip())\nresult = []\nfor i in range(testnum):\n\t(len1, num) = map(int, input().strip().split())\n\tposgun = list(map(int, input().strip().split()))\n\tNlist = [0] * len1\n\tfor j in range(num):\n\t\tNlist[posgun[j] - 1] = 1\n\tresult.append(solution(Nlist))\nfor i in result:\n\tprint(i)\n", "def timeOfFullFill(n, x, xlist):\n\tfirstDvalue = xlist[0] - 1\n\tlastDvalue = n - xlist[-1]\n\tdvalueList = [(xlist[i] - xlist[i - 1]) // 2 for i in range(1, x)]\n\tif len(dvalueList) != 0:\n\t\tresults.append(max([max(dvalueList), firstDvalue, lastDvalue]) + 1)\n\telse:\n\t\tresults.append(max([firstDvalue, lastDvalue]) + 1)\ntestNumber = int(input())\nresults = []\nfor i in range(testNumber):\n\t(n, x) = list(map(int, input().split()))\n\txlist = list(map(int, input().split()))\n\ttimeOfFullFill(n, x, xlist)\nfor i in results:\n\tprint(i)\n", "from math import ceil\n\ndef solve(g, c, m):\n\tgaps = [m[0] - 1, g - m[-1]]\n\tl = 0\n\tfor i in range(1, c):\n\t\tgaps.append(ceil((m[i] - m[i - 1] - 1) / 2))\n\tprint(max(gaps) + 1)\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\ta = [int(x) for x in input().split()]\n\tsolve(n, k, a)\n", "import sys, math\n\ndef max_time(n, k):\n\tif n == k:\n\t\treturn 1\n\twaterLoc = [0] * n\n\tfor j in range(k):\n\t\twaterLoc[int(tempLoc[j]) - 1] = 1\n\tmaxLoc = 0\n\tbeforeLoc = 0\n\tbeginFlag = False\n\tendFlag = False\n\tif waterLoc[0] == 0:\n\t\tbeginFlag = True\n\tif waterLoc[-1] == 0:\n\t\tendFlag = True\n\tsumOne = 0\n\tfor m in range(n):\n\t\tif waterLoc[m] == 1:\n\t\t\tif sumOne == 0 and beginFlag:\n\t\t\t\tmaxLoc = m + 1\n\t\t\t\tsumOne += 1\n\t\t\telse:\n\t\t\t\tsumOne += 1\n\t\t\t\tif (m - beforeLoc) % 2 == 0:\n\t\t\t\t\ttemp = int((m - beforeLoc) / 2 + 1)\n\t\t\t\telse:\n\t\t\t\t\ttemp = int(math.ceil((m - beforeLoc) / 2))\n\t\t\t\tmaxLoc = max(maxLoc, temp)\n\t\t\tbeforeLoc = m\n\tif endFlag:\n\t\tmaxLoc = max(maxLoc, n - beforeLoc)\n\treturn maxLoc\nnumTest = int(sys.stdin.readline())\nfor i in range(numTest):\n\ttemp = sys.stdin.readline().split(' ')\n\t(n, k) = (int(temp[0]), int(temp[1]))\n\ttempLoc = sys.stdin.readline().split(' ')\n\tprint(max_time(n, k))\n", "t = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\ts = list(map(int, input().split()))\n\ts.sort()\n\tres = s[0]\n\tfor i in range(1, len(s)):\n\t\tres = max(res, (s[i] - s[i - 1]) // 2 + 1)\n\tres = max(res, n - s[-1] + 1)\n\tprint(res)\n", "for num in range(int(input())):\n\tans = 0\n\tjoker = 0\n\t(n, k) = map(int, input().split())\n\ttap = input()\n\tlst = []\n\tif k == 1:\n\t\ttap = int(tap)\n\t\tans = 1 + max(tap - 1, n - tap)\n\t\tprint(ans)\n\t\tjoker = 1\n\telse:\n\t\ttap = tap.split()\n\t\tfor i in range(k):\n\t\t\tif i == 0:\n\t\t\t\tlst.append(int(tap[i]))\n\t\t\telse:\n\t\t\t\tm = int(tap[i]) - int(tap[i - 1])\n\t\t\t\tif m % 2 == 0:\n\t\t\t\t\tm = m / 2 + 1\n\t\t\t\t\tm = int(m)\n\t\t\t\t\tlst.append(m)\n\t\t\t\telse:\n\t\t\t\t\tm = (m + 1) / 2\n\t\t\t\t\tm = int(m)\n\t\t\t\t\tlst.append(m)\n\t\t\tv = n + 1 - int(tap[k - 1])\n\t\t\tlst.append(int(v))\n\tif joker == 0:\n\t\tprint(max(lst))\n", "t = int(input())\nlo = []\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tx = list(map(int, input().split()))\n\ta = [0] * n\n\tfor j in range(k):\n\t\ta[x[j] - 1] = 1\n\tl = 1\n\twhile 0 in a:\n\t\tfor j in range(n):\n\t\t\tif j + 1 < n and a[j + 1] == 1 or (a[j - 1] == 1 and j - 1 >= 0):\n\t\t\t\ta[j] = 2\n\t\tfor j in range(n):\n\t\t\tif a[j] == 2:\n\t\t\t\ta[j] = 1\n\t\tl += 1\n\tlo.append(l)\nprint('\\n'.join(map(str, lo)))\n"]

difficulty: EASY

source: codeforces

raw_problem:
A. Water The Garden

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

It is winter now, and Max decided it's about time he watered the garden.

The garden can be represented as n consecutive garden beds, numbered from 1 to n. k beds contain water taps (i-th tap is located in the bed xi), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed xi is turned on, then after one second has passed, the bed xi will be watered; after two seconds have passed, the beds from the segment [xi - 1, xi + 1] will be watered (if they exist); after j seconds have passed (j is an integer number), the beds from the segment [xi - (j - 1), xi + (j - 1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [xi - 2.5, xi + 2.5] will be watered after 2.5 seconds have passed; only the segment [xi - 2, xi + 2] will be watered at that moment.
  The garden from test 1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.   The garden from test 1 after 2 seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed.
Max wants to turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

Input

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 200).

Then t test cases follow. The first line of each test case contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n) — the number of garden beds and water taps, respectively.

Next line contains k integers xi (1 ≤ xi ≤ n) — the location of i-th water tap. It is guaranteed that for each  condition xi - 1 < xi holds.

It is guaranteed that the sum of n over all test cases doesn't exceed 200.

Note that in hacks you have to set t = 1.

Output

For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

Example

Input

3
5 1
3
3 3
1 2 3
4 1
1

Output

3
1
4

Note

The first example consists of 3 tests:

 There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds [1, 3] will be watered, and after 3 seconds pass, everything will be watered.

 There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes.

 There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.

question:
It is winter now, and Max decided it's about time he watered the garden.
The garden can be represented as n consecutive garden beds, numbered from 1 to n. k beds contain water taps (i-th tap is located in the bed x_{i}), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed x_{i} is turned on, then after one second has passed, the bed x_{i} will be watered; after two seconds have passed, the beds from the segment [x_{i} - 1, x_{i} + 1] will be watered (if they exist); after j seconds have passed (j is an integer number), the beds from the segment [x_{i} - (j - 1), x_{i} + (j - 1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [x_{i} - 2.5, x_{i} + 2.5] will be watered after 2.5 seconds have passed; only the segment [x_{i} - 2, x_{i} + 2] will be watered at that moment.
 ![image](1.png) The garden from test 1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.  ![image](2.png) The garden from test 1 after 2 seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed. Max wants to turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

Input
The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 200).
Then t test cases follow. The first line of each test case contains two integers n and k (1 ≤ n ≤ 200, 1 ≤ k ≤ n) — the number of garden beds and water taps, respectively.
Next line contains k integers x_{i} (1 ≤ x_{i} ≤ n) — the location of i-th water tap. It is guaranteed that for each ![image](3.png) condition x_{i - 1} < x_{i} holds.
It is guaranteed that the sum of n over all test cases doesn't exceed 200.
Note that in hacks you have to set t = 1.

Output
For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

Example
Input
3
5 1
3
3 3
1 2 3
4 1
1

Output
3
1
4

Note
The first example consists of 3 tests:
 -  There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds [1, 3] will be watered, and after 3 seconds pass, everything will be watered. -  There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes. -  There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.

image_tags:
Linear Data Structure
Linear Data Structure
Math

data_split: test