package main

import (
	"bufio"
	"os"
	"strconv"
)

const (
	MAXN  = 200000 + 5
	MAXPN = 20000000
	INF   = int32(2000000000)
)

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) NextInt() int {
	sign, val := 1, 0
	c, _ := fs.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, _ = fs.r.ReadByte()
	}
	if c == '-' {
		sign = -1
		c, _ = fs.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, _ = fs.r.ReadByte()
	}
	fs.r.UnreadByte()
	return sign * val
}

var seed uint32 = 2463534242

func rnd() int32 {
	seed ^= seed << 13
	seed ^= seed >> 17
	seed ^= seed << 5
	return int32(seed)
}

var pL = make([]int32, MAXPN)
var pR = make([]int32, MAXPN)
var pSz = make([]int32, MAXPN)
var pLazy = make([]int32, MAXPN)
var pVal = make([]int32, MAXPN)
var pMn = make([]int32, MAXPN)
var pPri = make([]int32, MAXPN)
var ptot int32

func pNew(v int32) int32 {
	ptot++
	x := ptot
	pVal[x] = v
	pMn[x] = v
	pSz[x] = 1
	pLazy[x] = 0
	pL[x] = 0
	pR[x] = 0
	pPri[x] = rnd()
	return x
}

func pClone(x int32) int32 {
	if x == 0 {
		return 0
	}
	ptot++
	y := ptot
	pL[y] = pL[x]
	pR[y] = pR[x]
	pSz[y] = pSz[x]
	pLazy[y] = pLazy[x]
	pVal[y] = pVal[x]
	pMn[y] = pMn[x]
	pPri[y] = pPri[x]
	return y
}

func pApply(x int32, add int32) {
	if x == 0 {
		return
	}
	pVal[x] += add
	pMn[x] += add
	pLazy[x] += add
}

func pPull(x int32) {
	l, r := pL[x], pR[x]
	pSz[x] = 1 + pSz[l] + pSz[r]
	mn := pVal[x]
	if l != 0 && pMn[l] < mn {
		mn = pMn[l]
	}
	if r != 0 && pMn[r] < mn {
		mn = pMn[r]
	}
	pMn[x] = mn
}

func pPush(x int32) {
	if x == 0 || pLazy[x] == 0 {
		return
	}
	if pL[x] != 0 {
		pL[x] = pClone(pL[x])
		pApply(pL[x], pLazy[x])
	}
	if pR[x] != 0 {
		pR[x] = pClone(pR[x])
		pApply(pR[x], pLazy[x])
	}
	pLazy[x] = 0
}

func pSplit(x int32, k int) (int32, int32) {
	if x == 0 {
		return 0, 0
	}
	x = pClone(x)
	pPush(x)
	if int(pSz[pL[x]]) >= k {
		a, b := pSplit(pL[x], k)
		pL[x] = b
		pPull(x)
		return a, x
	}
	a, b := pSplit(pR[x], k-int(pSz[pL[x]])-1)
	pR[x] = a
	pPull(x)
	return x, b
}

func pMerge(a, b int32) int32 {
	if a == 0 {
		return b
	}
	if b == 0 {
		return a
	}
	if pPri[a] > pPri[b] {
		a = pClone(a)
		pPush(a)
		pR[a] = pMerge(pR[a], b)
		pPull(a)
		return a
	}
	b = pClone(b)
	pPush(b)
	pL[b] = pMerge(a, pL[b])
	pPull(b)
	return b
}

func pFindFirstLess(root int32, v int32) int {
	if root == 0 {
		return 1
	}
	if pMn[root] >= v {
		return int(pSz[root]) + 1
	}
	x := root
	carry := int32(0)
	pos := 0
	for x != 0 {
		nextCarry := carry + pLazy[x]
		l := pL[x]
		if l != 0 && pMn[l]+nextCarry < v {
			x = l
			carry = nextCarry
			continue
		}
		if pVal[x]+carry < v {
			return pos + int(pSz[l]) + 1
		}
		pos += int(pSz[l]) + 1
		x = pR[x]
		carry = nextCarry
	}
	return pos + 1
}

func pKth(root int32, k int) int32 {
	if k == 0 {
		return INF
	}
	x := root
	carry := int32(0)
	for x != 0 {
		l := pL[x]
		ls := int(pSz[l])
		if k <= ls {
			carry += pLazy[x]
			x = l
		} else if k == ls+1 {
			return pVal[x] + carry
		} else {
			k -= ls + 1
			carry += pLazy[x]
			x = pR[x]
		}
	}
	return -INF
}

func pInsert(root int32, v int32) int32 {
	pos := pFindFirstLess(root, v)
	a, b := pSplit(root, pos-1)
	if b != 0 {
		b = pClone(b)
		pApply(b, 1)
	}
	mid := pNew(v)
	return pMerge(pMerge(a, mid), b)
}

var mL = make([]int32, MAXN)
var mR = make([]int32, MAXN)
var mSz = make([]int32, MAXN)
var mLazy = make([]int32, MAXN)
var mVal = make([]int32, MAXN)
var mMn = make([]int32, MAXN)
var mPri = make([]int32, MAXN)
var mtot int32

func mNew(v int32) int32 {
	mtot++
	x := mtot
	mVal[x] = v
	mMn[x] = v
	mSz[x] = 1
	mLazy[x] = 0
	mL[x] = 0
	mR[x] = 0
	mPri[x] = rnd()
	return x
}

func mApply(x int32, add int32) {
	if x == 0 {
		return
	}
	mVal[x] += add
	mMn[x] += add
	mLazy[x] += add
}

func mPull(x int32) {
	l, r := mL[x], mR[x]
	mSz[x] = 1 + mSz[l] + mSz[r]
	mn := mVal[x]
	if l != 0 && mMn[l] < mn {
		mn = mMn[l]
	}
	if r != 0 && mMn[r] < mn {
		mn = mMn[r]
	}
	mMn[x] = mn
}

func mPush(x int32) {
	if x == 0 || mLazy[x] == 0 {
		return
	}
	if mL[x] != 0 {
		mApply(mL[x], mLazy[x])
	}
	if mR[x] != 0 {
		mApply(mR[x], mLazy[x])
	}
	mLazy[x] = 0
}

func mSplit(x int32, k int) (int32, int32) {
	if x == 0 {
		return 0, 0
	}
	mPush(x)
	if int(mSz[mL[x]]) >= k {
		a, b := mSplit(mL[x], k)
		mL[x] = b
		mPull(x)
		return a, x
	}
	a, b := mSplit(mR[x], k-int(mSz[mL[x]])-1)
	mR[x] = a
	mPull(x)
	return x, b
}

func mMerge(a, b int32) int32 {
	if a == 0 {
		return b
	}
	if b == 0 {
		return a
	}
	if mPri[a] > mPri[b] {
		mPush(a)
		mR[a] = mMerge(mR[a], b)
		mPull(a)
		return a
	}
	mPush(b)
	mL[b] = mMerge(a, mL[b])
	mPull(b)
	return b
}

func mFindFirstLess(root int32, v int32) int {
	if root == 0 {
		return 1
	}
	if mMn[root] >= v {
		return int(mSz[root]) + 1
	}
	x := root
	carry := int32(0)
	pos := 0
	for x != 0 {
		nextCarry := carry + mLazy[x]
		l := mL[x]
		if l != 0 && mMn[l]+nextCarry < v {
			x = l
			carry = nextCarry
			continue
		}
		if mVal[x]+carry < v {
			return pos + int(mSz[l]) + 1
		}
		pos += int(mSz[l]) + 1
		x = mR[x]
		carry = nextCarry
	}
	return pos + 1
}

func mKth(root int32, k int) int32 {
	if k == 0 {
		return INF
	}
	x := root
	carry := int32(0)
	for x != 0 {
		l := mL[x]
		ls := int(mSz[l])
		if k <= ls {
			carry += mLazy[x]
			x = l
		} else if k == ls+1 {
			return mVal[x] + carry
		} else {
			k -= ls + 1
			carry += mLazy[x]
			x = mR[x]
		}
	}
	return -INF
}

func mInsert(root int32, v int32) int32 {
	pos := mFindFirstLess(root, v)
	a, b := mSplit(root, pos-1)
	if b != 0 {
		mApply(b, 1)
	}
	mid := mNew(v)
	return mMerge(mMerge(a, mid), b)
}

func eval(rootL, rootR int32, center int32, L int, l int) int32 {
	r := L - 1 - l
	ans := center
	cl := mKth(rootL, l)
	if cl != INF {
		if cl+1 < ans {
			ans = cl + 1
		}
	}
	cr := pKth(rootR, r)
	if cr != INF {
		if cr+1 < ans {
			ans = cr + 1
		}
	}
	return ans
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := in.NextInt()
	a := make([]int32, MAXN)
	rootsR := make([]int32, MAXN)

	for ; t > 0; t-- {
		n := in.NextInt()
		k := in.NextInt()
		L := n - k
		for i := 1; i <= n; i++ {
			a[i] = int32(in.NextInt())
		}

		ptot = 0
		mtot = 0

		rootsR[n+1] = 0
		for i := n; i >= 1; i-- {
			rootsR[i] = pInsert(rootsR[i+1], a[i])
		}

		var rootL int32 = 0
		var best int32 = 0

		for x := 1; x <= n; x++ {
			lmin := 0
			if v := L - 1 - (n - x); v > lmin {
				lmin = v
			}
			lmax := L - 1
			if x-1 < lmax {
				lmax = x - 1
			}
			if lmin <= lmax {
				rootR := rootsR[x+1]
				tpos := lmin - 1
				lo, hi := lmin, lmax
				for lo <= hi {
					mid := (lo + hi) >> 1
					if mKth(rootL, mid) >= pKth(rootR, L-1-mid) {
						tpos = mid
						lo = mid + 1
					} else {
						hi = mid - 1
					}
				}
				var cand int32
				if tpos < lmin {
					cand = eval(rootL, rootR, a[x], L, lmin)
				} else {
					cand = eval(rootL, rootR, a[x], L, tpos)
					if tpos+1 <= lmax {
						c2 := eval(rootL, rootR, a[x], L, tpos+1)
						if c2 > cand {
							cand = c2
						}
					}
				}
				if cand > best {
					best = cand
				}
			}
			rootL = mInsert(rootL, a[x])
		}

		out.WriteString(strconv.Itoa(int(best)))
		out.WriteByte('\n')
	}
}