At first, there was a legend related to the name of the problem, but now it's just a formal statement.

You are given $n$ points $a_1, a_2, \dots, a_n$ on the $OX$ axis. Now you are asked to find such an integer point $x$ on $OX$ axis that $f_k(x)$ is minimal possible.

The function $f_k(x)$ can be described in the following way:   form a list of distances $d_1, d_2, \dots, d_n$ where $d_i = |a_i - x|$ (distance between $a_i$ and $x$);  sort list $d$ in non-descending order;  take $d_{k + 1}$ as a result. 

If there are multiple optimal answers you can print any of them.


-----Input-----

The first line contains single integer $T$ ($ 1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent. 

The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.

It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them.


-----Example-----
Input
3
3 2
1 2 5
2 1
1 1000000000
1 0
4

Output
3
500000000
4

Difficulty: MEDIUM_HARD
Tags: Complete search

Sorting

Greedy algorithms
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mx = int(10000000000.0)
	ans = arr[0]
	for i in range(n - k):
		le = arr[i]
		r = arr[i + k]
		x = (le + r) // 2
		if mx > r - x:
			mx = r - x
			ans = x
	print(ans)


def main():
	buf = input()
	T = int(buf)
	n = []
	k = []
	a = []
	for i in range(T):
		buf = input()
		buflist = buf.split()
		n.append(int(buflist[0]))
		k.append(int(buflist[1]))
		buf = input()
		buflist = buf.split()
		a.append(list(map(int, buflist)))
	for i in range(T):
		a[i].sort()
	for i in range(T):
		minimum_point = (a[i][0] + a[i][k[i]]) // 2
		minimum_value = max(abs(a[i][0] - minimum_point), abs(a[i][k[i]] - minimum_point))
		for j in range(1, n[i] - k[i]):
			window_minimum_point = (a[i][j] + a[i][k[i] + j]) // 2
			window_minimum_value = max(abs(a[i][j] - window_minimum_point), abs(a[i][k[i] + j] - window_minimum_point))
			if window_minimum_value < minimum_value:
				minimum_point = window_minimum_point
				minimum_value = window_minimum_value
		print(minimum_point)

def __starting_point():
	main()
__starting_point()


out = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = min(((a[i] - a[i - k], a[i]) for i in range(k, n)))
	out.append(ans[1] - (ans[0] + 1) // 2)
print(*out)


_ = int(input().strip())
res = ''
for i in range(_):
	(n, k) = map(int, input().strip().split(' '))
	cnt = list(map(int, input().strip().split(' ')))
	mins = 1000000001
	ans = 0
	for j in range(n - k):
		if mins > cnt[j + k] - cnt[j]:
			mins = cnt[j + k] - cnt[j]
			ans = (cnt[j + k] + cnt[j]) // 2
	res += str(ans) + '\n'
print(res)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	a = [int(x) for x in input().strip().split()]
	a.sort()
	k = k + 1
	res = 10 ** 9 + 1
	for i in range(n - k + 1):
		dp = a[i + k - 1] - a[i]
		if res >= dp:
			ind = i
			res = dp
	fin = a[ind] + res // 2
	print(fin)


from collections import deque

def solve():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = min(((l[i] - l[i - k], l[i]) for i in range(k, n)))
	return ans[1] - (ans[0] + 1) // 2
out = deque()
for _ in range(int(input())):
	out.append(solve())
print(*out)


import sys
input = sys.stdin.readline
t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 100000000000
	for i in range(n - k):
		if ans > l[i + k] - l[i]:
			ind = i
			ans = l[i + k] - l[i]
	print(l[ind] + ans // 2)
	t -= 1


import sys
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
q = nn()
for _ in range(q):
	(n, k) = mi()
	l = lm()
	m = float('Inf')
	for i in range(0, n - k):
		if l[i + k] - l[i] < m:
			m = l[i + k] - l[i]
			x = (l[i + k] + l[i]) // 2
	print(x)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	tmp = 10 ** 18
	for i in range(n - k):
		if tmp > (a[i + k] - a[i] + 1) // 2:
			tmp = (a[i + k] - a[i] + 1) // 2
			ans = (a[i + k] - a[i] + 1) // 2 + a[i]
	print(ans)


import sys
import os
from io import BytesIO, IOBase

def cel(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return defaultdict(int)

def ddl():
	return defaultdict(list)

def ddd():
	return defaultdict(defaultdict(int))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
for _ in range(ii()):
	(n, k) = mi()
	a = li()
	mn = 10 ** 9
	ans = 0
	for i in range(n - k):
		tmp = (a[i] + a[i + k]) // 2
		if max(a[i + k] - tmp, tmp - a[i]) < mn:
			mn = max(a[i + k] - tmp, tmp - a[i])
			ans = tmp
	print(ans)


t = int(input())
out = [0] * t
for u in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	best = float('inf')
	coord = None
	for i in range(n - k):
		if a[i + k] - a[i] < best:
			coord = (a[i + k] + a[i]) // 2
			best = a[i + k] - a[i]
	out[u] = coord
print(*out, sep='\n')


from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()
for _ in range(t):
	(n, k) = gil()
	a = gil()
	(d, ans) = (inf, -1)
	for i in range(k, n):
		x = (a[i - k] + a[i]) // 2
		nd = a[i] - a[i - k]
		if d > nd:
			ans = x
			d = nd
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = 10 ** 18
	x = -1
	for i in range(n - k):
		if abs(a[i + k] - a[i]) < d:
			d = abs(a[i + k] - a[i])
			x = a[i] + (a[i + k] - a[i]) // 2
	print(x)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(RL())

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	for _ in range(N()):
		(n, k) = RL()
		arr = RLL()
		arr.sort()
		res = INF
		dif = INF
		for i in range(k, n):
			dis = arr[i] - arr[i - k]
			mid = dis // 2 + arr[i - k]
			ma = max(abs(mid - arr[i]), abs(mid - arr[i - k]))
			if ma < dif:
				dif = ma
				res = mid
		print(res)
main()


def fk(n, l1, k):
	if k == 0:
		return str(l1[0])
	mi = l1[-1] - l1[0] + 1
	p = 0
	for i in range(n - k):
		if l1[i + k] - l1[i] < mi:
			mi = l1[i + k] - l1[i]
			p = l1[i + k] + l1[i] >> 1
	return str(p)
t = int(input())
l = []
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	l.append(fk(n, l1, k))
print('\n'.join(l))


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def dinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def main():
	for i in range(dinput()):
		(leonov, leonov1) = rinput()
		a = list(rinput())
		print(min(((a[i] - a[i - leonov1], a[i]) for i in range(leonov1, leonov)))[1] - (min(((a[i] - a[i - leonov1], a[i]) for i in range(leonov1, leonov)))[0] + 1) // 2)
main()


def solve(n, k, ary):
	if k == 0:
		return ary[0]
	cur = ary[k] - ary[0]
	tmp = cur
	idx = 0
	for i in range(k + 1, n):
		cur = ary[i] - ary[i - k]
		if cur < tmp:
			tmp = cur
			idx = i - k
	mid = tmp // 2
	return ary[idx] + mid

def stdin():
	cases = int(input())
	outs = []
	for i in range(cases):
		nk = input()
		if nk == '1 0':
			res = input()
		else:
			(n, k) = nk.split(' ', 1)
			ary = list(map(int, input().split()))
			res = solve(int(n), int(k), ary)
		outs.append(res)
	print(*outs)
stdin()


import os
from io import BytesIO, StringIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
DEBUG = False
debug_print = print if DEBUG else lambda *x, **y: None

def input_as_list():
	return list(map(int, input().split()))

def array_of(f, *dim):
	return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
	T = int(input())
	out = []
	for _ in range(T):
		(n, k) = input_as_list()
		a = input_as_list()
		if k == 0:
			out.append(str(a[0]))
		else:
			min_val = 1000000000
			min_idx = 0
			for i in range(n - k):
				val = a[i + k] - a[i]
				if val < min_val:
					min_val = val
					min_idx = a[i] + val // 2
			out.append(str(min_idx))
	print('\n'.join(out))
main()


import sys
import math

def main():
	t = int(sys.stdin.readline().rstrip())
	inputs = sys.stdin.read().split('\n')
	for row in range(0, t):
		(p, k) = [int(x) for x in inputs[2 * row].split(' ')]
		nums = [int(x) for x in inputs[2 * row + 1].split(' ')]
		d = 999999999999999999
		for i in range(k, p):
			curr = (nums[i] - nums[i - k] + 1) // 2
			if curr < d:
				d = curr
				ans = nums[i] - d
		print(ans)
main()


import sys
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		self._solve()

	def _solve(self):
		t = int(input())
		for _ in range(t):
			(n, k) = [int(item) for item in input().split()]
			a = [int(item) for item in input().split()]
			a.sort()
			mn = float('inf')
			idx = -1
			for i in range(n - k):
				if a[i + k] - a[i] < mn:
					mn = a[i + k] - a[i]
					idx = i
			print(a[idx] + a[idx + k] >> 1)

def main():
	problem = Problem()
	problem.solve()

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
import bisect
T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 10000000000
	for i in range(n - k):
		if ans > a[i + k] - a[i]:
			ansindex = i
			ans = a[i + k] - a[i]
	print(a[ansindex] + ans // 2)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	A = [int(a) for a in input().split()]
	B = [A[i + K] - A[K] for i in range(N - K)]
	mi = 10 ** 20
	mx = -1
	for i in range(N - K):
		if A[i + K] - A[i] < mi:
			mi = A[i + K] - A[i]
			mx = (A[i + K] + A[i]) // 2
	print(mx)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(''.join([str(x) for x in a]) + '\n')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
t = int(input())
for _ in range(t):
	(n, k) = li()
	a = li()
	a.sort()
	ans = 10000000000000000
	v = 1000000000000000000
	for i in range(n - k):
		m = a[i + k] - a[i]
		if m < v:
			v = m
			ans = (a[i + k] + a[i]) // 2
	print(ans)


from sys import stdin

def solve(l, n, k):
	min_d = l[n - 1]
	min_idx = 0
	for i in range(n - k):
		dist = l[i + k] - l[i]
		if dist < min_d:
			min_d = dist
			min_idx = i
	res = l[min_idx] + min_d // 2
	return res
t = int(input())
res = []
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	l = [int(x) for x in stdin.readline().split()]
	res.append(solve(l, n, k))
print(*res)


I = lambda : list(map(int, input().split()))
import sys, math as mt
input = sys.stdin.readline
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = mt.inf
	for i in range(k, n):
		if a[i] - a[i - k] < ans:
			ans = a[i] - a[i - k]
			an = (a[i] + a[i - k]) // 2
	print(an)


from sys import stdin, stdout
import math, queue, heapq
fastinput = stdin.readline
fastout = stdout.write

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def computeLPSArray(pat, M, lps):
	len = 0
	lps[0]
	i = 1
	while i < M:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
t = int(fastinput())
mod = 10 ** 9 + 7
while t:
	t -= 1
	(n, k) = map(int, fastinput().split())
	a = list(map(int, fastinput().split()))
	ans = [mod, mod]
	for i in range(0, n - k):
		dist = a[i + k] - a[i]
		ans = min(ans, [dist, a[i] + dist // 2])
	print(ans[1])


import math
import sys
input = sys.stdin.buffer.readline
t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	mini_val = float('inf')
	index = -1
	for i in range(k, n):
		p = math.ceil((list1[i] + list1[i - k]) / 2)
		q = math.floor((list1[i] + list1[i - k]) / 2)
		temp = min(max(p - list1[i - k], list1[i] - p), max(q - list1[i - k], list1[i] - q))
		if temp < mini_val:
			mini_val = temp
			if temp == min(p - list1[i - k], list1[i] - p):
				index = p
			else:
				index = q
	print(index)
	t -= 1


import math
from sys import stdin
numQueries = int(input())
for i in range(numQueries):
	(n, k) = [int(x) for x in stdin.readline().rstrip().split()]
	numbers = [int(x) for x in stdin.readline().rstrip().split()]
	result = -1
	dist = math.inf
	for i in range(n - k):
		current = numbers[i]
		nxt = numbers[i + k]
		delta = (nxt - current) / 2
		if delta < dist:
			dist = delta
			result = (current + nxt) / 2
	print(int(result))


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	(n, k) = list(map(int, sys.stdin.readline().strip().split()))
	a = list(map(int, sys.stdin.readline().strip().split()))
	i = 0
	j = k
	M = 10 ** 10
	while j < n:
		if a[j] - a[i] < M:
			M = a[j] - a[i]
			x = (a[j] + a[i]) // 2 + (a[j] + a[i]) % 2
		i = i + 1
		j = j + 1
	print(x)


ans = ''
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	m = 1000000001
	x = 0
	for i in range(n - k):
		if m > a[i + k] - a[i]:
			m = a[i + k] - a[i]
			x = (a[i + k] + a[i]) // 2
	ans += str(x) + '\n'
print(ans)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		p = list(map(int, input().split()))
		(mi, x) = (inf, 0)
		for i in range(n - k):
			if mi > p[i + k] - p[i]:
				mi = p[i + k] - p[i]
				x = p[i] + (p[i + k] - p[i]) // 2
		print(x)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
s = ''
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	Min = 1000000001
	ans = a[0]
	for (x, y) in zip(a[:-k], a[k:]):
		if y - x < Min:
			ans = (x + y) // 2
			Min = y - x
	s += str(ans) + '\n'
print(s)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 10 ** 10
	if n == 1:
		print(A[0])
	else:
		for i in range(n - k):
			if ans > A[i + k] - A[i]:
				m = i
				ans = A[i + k] - A[i]
		print((A[m + k] + A[m]) // 2)


from math import *
from sys import stdin, stdout
for t in range(int(input())):
	(n, k) = map(int, stdin.readline().split())
	L = list(map(int, stdin.readline().split()))
	curMin = inf
	ind = None
	for i in range(n - k):
		if L[i + k] - L[i] < curMin:
			curMin = L[i + k] - L[i]
			ind = i
	stdout.write(str((L[ind] + L[ind + k]) // 2) + '\n')


import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def solve2():
	(n, k) = list(map(int, input().split()))
	L = list(map(int, input().split()))
	ans = float('inf')
	ans_x = -1
	for i in range(n - k):
		l = L[i]
		r = L[i + k]
		tmp = (r + l) // 2
		tmp_ans = max(r - tmp, tmp - l)
		if ans > tmp_ans:
			ans = tmp_ans
			ans_x = tmp
	print(ans_x)
n = int(input())
for _ in range(n):
	solve2()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	best = 10000000000
	for i in range(n - k):
		if aa[i + k] - aa[i] < best:
			best = aa[i + k] - aa[i]
			bestpos = i
	print(aa[bestpos] + best // 2)


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *
from heapq import *
from itertools import permutations

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)

def bo(i):
	return ord(i) - ord('a')
t = fi()
while t > 0:
	t -= 1
	(n, k) = mi()
	a = li()
	a.sort()
	mini = [10 ** 18, 10 ** 18]
	for i in range(n):
		if i >= k:
			g = (a[i] + a[i - k]) // 2
			p = max(abs(g - a[i]), abs(g - a[i - k]))
			if p < mini[0]:
				mini[0] = p
				mini[1] = g
	print(mini[1] if k > 0 else a[0])


import sys
import io, os
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	m = 10 ** 18
	x = -1
	for i in range(n - k):
		if A[i + k] - A[i] < m:
			x = A[i] + (A[i + k] - A[i]) // 2
			m = A[i + k] - A[i]
	print(x)


def main():
	inp = readnumbers()
	ii = 0
	T = inp[ii]
	ii += 1
	for _ in range(T):
		n = inp[ii]
		ii += 1
		k = inp[ii]
		ii += 1
		a = inp[ii:ii + n]
		ii += n
		ans = min(((a[i] - a[i - k], a[i]) for i in range(k, n)))
		print(ans[1] - (ans[0] + 1) // 2)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


import os, sys
from io import BytesIO, IOBase

def check(mid, arr, k):
	(i, j) = (0, 0)
	while j != len(arr) and arr[j] - arr[i] <= 2 * mid:
		j += 1
	ans = j - i
	ind = (arr[i] + arr[j - 1]) // 2
	while j != len(arr):
		i = i + 1
		j = max(j, i + 1)
		while j != len(arr) and arr[j] - arr[i] <= 2 * mid:
			j += 1
		if ans < j - i:
			ans = j - i
			ind = (arr[i] + arr[j - 1]) // 2
	if ans <= k:
		return 0
	return ind + 1

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		(hi, lo, ans) = (10 ** 9, 0, 10 ** 10)
		while hi >= lo:
			mid = (hi + lo) // 2
			x = check(mid, a, k)
			if x:
				hi = mid - 1
				ans = x - 1
			else:
				lo = mid + 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import *
import os, sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
r = lambda dtype: dtype(input().strip())
rd = lambda dtype: [dtype(x) for x in input().split()]
r2d = lambda dtype, n: [r(dtype) for _ in range(n)]
rs2d = lambda dtype, n: [rd(dtype) for _ in range(n)]
r_enu = lambda dtype: [(i, x) for (i, x) in enumerate(rd(dtype))]
rs_enu = lambda dtype, n: [[i, rd(dtype)] for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
for _ in range(r(int)):
	(n, k) = rd(int)
	(a, ans) = (rd(int), [0, float('inf')])
	for i in range(k, n):
		md = a[i - k] + a[i] >> 1
		val = max(md - a[i - k], a[i] - md)
		if val < ans[-1]:
			ans = [md, val]
	print(ans[0])


def solve(points, k, res):
	if k == 0:
		res.append(points[0])
		return
	min_diff = float('inf')
	n = len(points)
	for i in range(n - k):
		p1 = points[i]
		p2 = points[i + k]
		avg = (p1 + p2) // 2
		diff = max(abs(avg - p1), abs(avg - p2))
		if diff < min_diff:
			ans = avg
			min_diff = diff
	res.append(ans)

def main():
	t = int(input())
	res = []
	for i in range(t):
		(n, k) = map(int, input().split())
		points = list(map(int, input().split()))
		solve(points, k, res)
	for i in res:
		print(i)
main()


out = []
for tt in range(int(input())):
	(n, m) = map(int, input().split())
	line = list(map(int, input().split()))
	(i, maxn) = (0, 1061109567)
	ans = 0
	while i + m < n:
		if line[i + m] - line[i] < maxn:
			maxn = line[i + m] - line[i]
			ans = (line[i + m] + line[i]) // 2
		i += 1
	out.append(ans)
print(*out)


def funk():
	nonlocal m
	(n, k) = map(int, input().split())
	mass = [int(i) for i in input().split()]
	x = 0
	minn = 10 ** 9
	for i in range(n - k):
		q = mass[i]
		j = mass[i + k]
		if j - q < minn:
			(minn, x) = (j - q, (j + q) // 2)
	m.append(x)
t = int(input())
m = []
for i in range(t):
	funk()
for i in m:
	print(i)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ans = 0
	m = 10 ** 18
	for i in range(n - k):
		D = a[k + i] - a[i]
		if (D + 1) // 2 < m:
			m = (D + 1) // 2
			ans = a[i] + m
	print(ans)


INF = 10 ** 10
t = int(input())
ans = []
for w in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	dist = INF
	point = int(0)
	for i in range(n - k):
		if a[i + k] - a[i] < dist:
			dist = a[i + k] - a[i]
			point = (a[i + k] + a[i]) // 2
	ans.append(point)
for elem in ans:
	print(elem)


def electrification(lst, n, k):
	(min_elem, min_ind) = (lst[-1], 0)
	for i in range(n - k):
		dist = lst[i + k] - lst[i]
		if dist < min_elem:
			(min_elem, min_ind) = (dist, i)
	return lst[min_ind] + min_elem // 2
t = int(input())
a = list()
for j in range(t):
	(N, K) = [int(x) for x in input().split()]
	b = [int(y) for y in input().split()]
	a.append(electrification(b, N, K))
for elem in a:
	print(elem)


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self):
		return sys.stdin.readline().split()

	def next_ints(self):
		return [int(x) for x in sys.stdin.readline().split()]

	def next_int(self):
		return int(self.next())

	def solve(self):
		ca = self.next_int()
		for _ in range(ca):
			(n, k) = self.next_ints()
			a = self.next_ints()
			ii = 0
			for i in range(0, n - k):
				if a[i + k] - a[i] < a[ii + k] - a[ii]:
					ii = i
			print((a[ii] + a[ii + k]) // 2)
Main().solve()


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	b = sorted(list(map(int, input().split())))
	i = 0
	m = 100000000000000
	while i < n - k:
		l = b[i + k] - b[i]
		if l < m:
			m = l
			q = (b[i] + b[i + k]) // 2
		i += 1
	print(q)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
inf = int(10 ** 20)
max_val = inf
min_val = -inf
RW = lambda : sys.stdin.readline().strip()
RI = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]
nb_test = RI()
for _ in range(nb_test):
	(lens, k) = RMI()
	arrs = sorted(RMI())
	ans = arrs[0]
	max_diff = arrs[-1] - arrs[0]
	for i in range(lens - k):
		curr = arrs[i + k] - arrs[i]
		if curr <= max_diff:
			max_diff = curr
			ans = (arrs[i + k] + arrs[i]) // 2
	print(ans)


import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)
t = read_int()
for _ in range(t):
	(n, k) = read_int_list()
	arr = read_int_list()
	ans = mini = float('inf')
	if n == 1:
		print(arr[0])
		continue
	for i in range(n - k):
		a = (arr[i] + arr[i + k]) // 2
		diff = max(a - arr[i], arr[i + k] - a)
		mini = min(mini, diff)
		if diff == mini:
			ans = a
	print(ans)


import sys
input = sys.stdin.readline
Query = int(input())
for query in range(Query):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	L = 10 ** 15
	for i in range(k, n):
		if A[i] - A[i - k] < L:
			L = A[i] - A[i - k]
			ANS = (A[i] + A[i - k]) // 2
	print(ANS)


import sys
input = sys.stdin.readline
t = int(input())
li = [list(map(int, input().split())) for i in range(2 * t)]
for i in range(t):
	(n, k) = (li[i * 2][0], li[i * 2][1])
	ans = 10 ** 10
	j = 0
	item = 0
	while j + k < n:
		if -(-(li[i * 2 + 1][j + k] - li[i * 2 + 1][j]) // 2) < ans:
			ans = -(-(li[i * 2 + 1][j + k] - li[i * 2 + 1][j]) // 2)
			item = (li[i * 2 + 1][j + k] + li[i * 2 + 1][j]) // 2
		j += 1
	print(item)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	l = sorted(I())
	d = 10 ** 9 + 10
	an = l[0]
	le = r = 0
	for i in range(n - k):
		le = l[i]
		r = l[i + k]
		x = (le + r) // 2
		if d > r - x:
			an = x
			d = r - x
	print(an)


from sys import stdin

def solve():
	results = []
	for _ in range(int(stdin.readline())):
		(n, k) = map(int, stdin.readline().split())
		a = [int(x) for x in stdin.readline().split()]
		(i, s) = (0, 0)
		while i + k < n:
			if a[i + k] - a[i] < a[s + k] - a[s]:
				s = i
			i += 1
		results.append((a[s] + a[s + k]) // 2)
	print('\n'.join(map(str, results)))
solve()


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a.sort()
	ans = -1
	val = 10 ** 10
	for i in range(k, n):
		curr = a[i] - a[i - k]
		if val > curr:
			val = curr
			ans = (a[i] + a[i - k]) // 2
	print(ans)


import sys
for w in range(int(input())):
	(n, k) = [int(i) for i in sys.stdin.readline().split()]
	data = [int(i) for i in sys.stdin.readline().split()]
	mn = float('inf')
	x = 0
	for i in range(n - k):
		a = data[i + k] - data[i]
		if a < mn:
			mn = a
			x = i
	print((data[x] + data[x + k]) // 2)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, K) = getInts()
	A = getInts()
	diff = 10 ** 18
	idx = -1
	for i in range(N - K):
		if A[i + K] - A[i] < diff:
			diff = A[i + K] - A[i]
			idx = i
	return A[idx] + diff // 2
for _ in range(getInt()):
	print(solve())


from sys import stdin, stdout
input = stdin.readline
print = stdout.write

def solve(a, k):
	res = (a[k] - a[0]) / 2
	x = (a[k] + a[0]) // 2
	for i in range(1, len(a) - k):
		if (a[k + i] - a[i]) / 2 < res:
			res = (a[k + i] - a[i]) / 2
			x = (a[k + i] + a[i]) // 2
	return x
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(str(solve(a, k)) + '\n')


import sys
inf = 10 ** 9 + 1
t = int(input())
res = []
lines = sys.stdin.readlines()
for e in range(t):
	(n, k) = map(int, lines[e * 2].split())
	aa = list(map(int, lines[e * 2 + 1].split()))
	fx = inf
	x = None
	for i in range(k, n):
		x_tmp = aa[i - k] + aa[i] >> 1
		fx_tmp = max(abs(aa[i - k] - x_tmp), abs(aa[i] - x_tmp))
		if fx_tmp < fx:
			x = x_tmp
			fx = fx_tmp
	res.append(str(x))
print('\n'.join(res))


from sys import stdin
input = stdin.readline
m = 2 ** 32 - 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = (a[k] + a[0]) // 2
	ra = a[k] - a[0]
	for i in range(n - k):
		if a[i + k] - a[i] < ra:
			ra = a[i + k] - a[i]
			ans = (a[i + k] + a[i]) // 2
	print(ans)


from math import ceil
from sys import stdin, stdout
t = int(input())
while t > 0:
	(n, k) = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	if k == 0:
		print(a[0])
	else:
		l = 0
		r = k
		m = 100000000000
		ans = 0
		for i in range(n - k):
			mid = ceil((a[l] + a[r]) / 2)
			m1 = abs(a[l] - mid)
			m2 = abs(a[r] - mid)
			if m1 + m2 < m:
				curr = m1 + m2
				m = curr
				ans = mid
			l += 1
			r += 1
		print(ans)
	t -= 1


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	m = 10 ** 9
	ans = -1
	for i in range(k, n):
		dist = l[i] - l[i - k]
		if dist < m:
			m = dist
			ans = l[i - k] + dist // 2
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ans = 0
	m = 10 ** 18
	for i in range(n - k):
		D = a[k + i] - a[i]
		if (D + 1) // 2 < m:
			m = (D + 1) // 2
			ans = a[i] + m
	print(ans)


from sys import stdin, stdout
T = int(input())
for i in range(T):
	(N, K) = [int(x) for x in stdin.readline().split()]
	arr = [int(x) for x in stdin.readline().split()]
	arr.sort()
	res = 99999999999
	x = 0
	for i in range(N):
		if i + K >= N:
			break
		else:
			A = arr[i]
			B = arr[i + K]
			d = B - A
			if d % 2 == 1:
				d = d // 2 + 1
			else:
				d = d // 2
			if d < res:
				res = d
				x = (A + B) // 2
	print(x)


final_ans = []
times = int(input())
for i in range(times):
	(n, k) = map(int, input().split(' '))
	a = [*map(int, input().split(' '))]
	ans = min(((a[i] - a[i - k], a[i]) for i in range(k, n)))
	final_ans.append(ans[1] - (ans[0] + 1) // 2)
for number in final_ans:
	print(number)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	q = a[k] - a[0]
	an = a[0] + (a[k] - a[0]) // 2
	for j in range(1, n - k):
		p = a[j + k] - a[j]
		if p < q:
			q = p
			an = a[j] + p // 2
	print(an)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if k == 0:
		print(A[0])
		continue
	m = 10 ** 18
	x = -1
	for i in range(n - k):
		if A[i + k] - A[i] < m:
			x = A[i] + (A[i + k] - A[i]) // 2
			m = A[i + k] - A[i]
	print(x)


t = int(input())
answers = []
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	min_koor = 0
	min_dist = a[n - 1] - a[0]
	for j in range(0, n - k):
		if a[j + k] - a[j] <= min_dist:
			min_dist = a[j + k] - a[j]
			min_koor = (a[j] + a[j + k]) / 2
	answers.append(min_koor)
for i in answers:
	print(int(i))


import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

class Problem:

	def __init__(self):
		(self.n, self.k) = R()
		self.a = L()
		self.a.sort()

	def solve(self):
		ans = 0
		mn = 10 ** 10
		for i in range(self.n - self.k):
			if self.a[i + self.k] - self.a[i] < mn:
				mn = self.a[i + self.k] - self.a[i]
				ans = (self.a[i + self.k] + self.a[i]) // 2
		print(ans)
		return
for i in range(I()):
	p = Problem()
	p.solve()


import sys
input = sys.stdin.readline

def judge(v):
	for i in range(n - k + 1):
		x = (a[i] + a[i + k - 1]) // 2
		if max(x - a[i], a[i + k - 1] - x) <= v:
			return True
	return False

def binary_search():
	(l, r) = (0, 10 ** 9)
	while l <= r:
		mid = (l + r) // 2
		flag = judge(mid)
		if flag:
			r = mid - 1
		else:
			l = mid + 1
	return l
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	k += 1
	a = list(map(int, input().split()))
	v = binary_search()
	for i in range(n - k + 1):
		x = (a[i] + a[i + k - 1]) // 2
		if max(x - a[i], a[i + k - 1] - x) <= v:
			print(x)
			break


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		(n, k) = ria()
		a = ria()
		mi = 9999999999999999999999999999
		for i in range(k, n):
			f = a[i] - a[i - k]
			if f < mi:
				mi = f
				x = (a[i] + a[i - k]) // 2
		print(x)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mn = float('inf')
	d = float('inf')
	for i in range(n - k):
		tmp = abs(a[i] - a[i + k])
		if d > tmp:
			d = tmp
			mn = tmp // 2 + a[i]
	print(mn)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def bfs(adj, peoples):
	stack = [0]
	order = []
	parent = [-1] * len(adj)
	subt = peoples[:]
	while stack:
		v = stack.pop()
		order.append(v)
		for dest in adj[v]:
			if parent[v] == dest:
				continue
			parent[dest] = v
			stack.append(dest)
	for v in reversed(order):
		if v != 0:
			subt[parent[v]] += subt[v]
	return (order, subt, parent)

def main():
	t = int(input())
	ans = [0] * t
	for ti in range(t):
		(n, k) = map(int, input().split())
		a = tuple(map(int, input().split())) + (10 ** 10,)
		(ok, ng, res) = (10 ** 9, -1, 0)
		while abs(ok - ng) > 1:
			mid = ok + ng >> 1
			r = 0
			for l in range(n):
				while a[r] <= a[l] + 2 * mid:
					r += 1
				if r - l > k:
					(ok, res) = (mid, a[l] + mid)
					break
			else:
				ng = mid
		ans[ti] = res
	sys.stdout.buffer.write(('\n'.join(map(str, ans)) + '\n').encode('utf-8'))
main()


import math
t = int(input())
u = []
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(i, m) = (0, math.inf)
	h = 0
	while i + k < n:
		if a[i + k] - a[i] < m:
			m = a[i + k] - a[i]
			h = (a[i + k] + a[i]) // 2
		i += 1
	u.append(h)
print(*u)


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	Query.append([N, K, A])
INF = 10 ** 14
for (N, K, A) in Query:
	A.sort()
	D = INF
	for i in range(N - K):
		if A[i + K] - A[i] < D:
			D = A[i + K] - A[i]
			ans = (A[i + K] + A[i]) // 2
	print(ans)


T = int(input())
import sys
res = []
for t in range(T):
	(N, K) = map(int, sys.stdin.readline().split())
	a_list = list(map(int, sys.stdin.readline().split()))
	if N == 1:
		res.append(a_list[0])
		continue
	ans = float('inf')
	ans_i = -1
	for i in range(N - K):
		tmp = abs(a_list[i + K] - a_list[i])
		if ans > tmp:
			ans = tmp
			ans_i = i
	res.append((a_list[ans_i + K] + a_list[ans_i]) // 2)
for r in res:
	print(r)


pp = []
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	x = 10 ** 10
	d = 0
	for i in range(n - k):
		if a[i + k] - a[i] < x:
			x = a[i + k] - a[i]
			d = (a[i + k] + a[i]) // 2
	pp.append(d)
for i in pp:
	print(i)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = 999999999999999999999
	ans = -1
	for j in range(n - k):
		s = (l[j] + l[j + k]) // 2
		if max(l[j + k] - s, s - l[j]) < m:
			m = max(l[j + k] - s, s - l[j])
			ans = s
	print(ans)


import sys, os, io
sys.stdin = io.BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = io.BytesIO()
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = min(((a[i] - a[i - k], a[i]) for i in range(k, n)))
	sys.stdout.write(str(ans[1] - (ans[0] + 1) // 2).encode('ascii'))
	sys.stdout.write(b'\n')
os.write(1, sys.stdout.getvalue())


import sys
input = sys.stdin.readline
t = int(input())
for k in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	mx = 10000000000000000
	for i in range(n - k):
		if a[i + k] - a[i] < mx:
			s = i
			mx = a[i + k] - a[i]
	print(a[s] + mx // 2)


t = int(input())
Ans = []
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	mini = 100000000000
	for i in range(n - k):
		y1 = (-A[i] + A[i + k] - 1) / 2
		y2 = (-A[i] + A[i + k]) / 2
		if float.is_integer(y1):
			if mini > y1 + 1:
				ans = A[i] + y1
				mini = y1 + 1
		elif float.is_integer(y2):
			if mini > y2:
				ans = A[i] + y2
				mini = y2
	Ans.append(int(ans))
print(*Ans, sep='\n')


n = int(input())
a = []
b = []
c = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
	x = list(map(int, input().split()))
	c.append(x)
for i in range(n):
	c[i].sort()
for i in range(n):
	mn = (c[i][0] + c[i][b[i]]) // 2
	mnz = max(abs(c[i][0] - mn), abs(c[i][b[i]] - mn))
	for j in range(1, a[i] - b[i]):
		tc = (c[i][j] + c[i][b[i] + j]) // 2
		tcz = max(abs(c[i][j] - tc), abs(c[i][b[i] + j] - tc))
		if tcz < mnz:
			mn = tc
			mnz = tcz
	print(mn)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(d, x) = (10 ** 9, 0)
	for i in range(n - k):
		d2 = a[i + k] - a[i] + 1 >> 1
		if d2 < d:
			d = d2
			x = a[i + k] + a[i] >> 1
	print(x)