You are given $N$ integers in an array: $A[1], A[2], \ldots, A[N]$. You also have another integer $L$.
Consider a sequence of indices ($i_1, i_2, \ldots, i_k$). Note that a particular index can occur multiple times in the sequence, and there is no order in which these indices have to occur. ($i_1, i_2, \ldots, i_k$) is a sequence of size $k$. It is said to be an $Interesting$ sequence, if $A[i_1] \ge A[i_2] \ge \ldots \ge A[i_k]$.
The $Cost$ of an Interesting sequence ($i_1, i_2, \ldots, i_k$), is defined to be the minimum absolute difference between any two adjacent indices. In other words, the Cost is $min \{ |i_2 - i_1|, |i_3 - i_2|, \ldots, |i_k - i_{k-1}| \}$.
Your job is to consider the Costs of all the Interesting sequences of size $L$ associated with the given array, and output the maximum Cost. Note that you can show that there is always at least one Interesting sequence for the given constraints.

-----Input-----
- The first line contains a single integer, $T$, which is the number of testcases. The description of each testcase follows.
- The first line of each testcase contains two space separated integers: $N$ and $L$.
- The second line of each testcase contains $N$ space separated integers: $A[1], A[2], \ldots, A[N]$.

-----Output-----
- For each testcase, output the answer in a new line.

-----Constraints-----
- $1 \leq T \leq 3$
- $1 \leq A[i] \leq 10^9$
- $2 \leq L \leq 10^9$

-----Subtasks-----
- Subtask 1: 7 points
- It is guaranteed that $A[1] > A[2] > \ldots > A[N]$
- Note that the above condition implies that all elements are distinct.
- $1 \leq N \leq 500$
- Subtask 2: 7 points
- It is guaranteed that $A[1] \ge A[2] \ge \ldots \ge A[N]$
- $1 \leq N \leq 500$
- Subtask 3: 14 points
- It is guaranteed that all elements are distinct.
- $1 \leq N \leq 500$
- Subtask 4: 14 points
- $1 \leq N \leq 500$
- Subtask 5: 25 points
- It is guaranteed that all elements are distinct.
- $1 \leq N \leq 3000$
- Subtask 6: 33 points
- $1 \leq N \leq 3000$

-----Sample Input-----
1
6 3
2 4 1 12 3 5

-----Sample Output-----
3

-----Explanation-----
We are looking for Interesting sequences of length 3. Some of them are:
- (4, 2, 3): This is Interesting because $A[4] \ge A[2] \ge A[3]$. Its cost is $min \{ |2-4|, |3-2|\} = 1$.
- (5, 1, 1): Cost is 0.
- (2, 2, 2): Cost is 0.
- (6, 1, 3): Cost is 2.
- (6, 2, 5): Cost is 3.
There are other Interesting Sequences of length 3 as well. But if you list them all out, you'll see that the maximum Cost is 3. Hence the answer is 3.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\n# from queue import PriorityQueue\nimport bisect\nfor _ in range(int(input())):\n    n,l = map(int, input().split())\n    a_l = list(map(int, input().split()))\n    \n    dic = {}\n    dif = 0\n    for i,v in enumerate(a_l, start=1):\n        if v not in dic:\n            dic[v] = [i, i]\n        else:\n            dic[v][0] = min(dic[v][0], i)\n            dic[v][1] = max(dic[v][1], i)\n            dif = max(dif, dic[v][1]-dic[v][0])\n            \n    ans = dif\n    if l <= len(set(a_l)):\n        i_l = [[v,i] for i,v in enumerate(a_l, start=1)]\n        i_l.sort(reverse=True)\n        \n        dp = [[-1 for _ in range(l)] for _ in range(n)]\n        pq_l = [[] for _ in range(l)]\n        for i in range(1,n):\n            il = 1\n            dif_l = []\n            for j in range(i):\n                dif = abs(i_l[i][1]-i_l[j][1])\n                dif_l.append(dif)\n                dp[i][il] = max(dp[i][il], dif)\n                \n            for il in range(2,min(l,i+1)):\n                for prev_max, ind in reversed(pq_l[il-1]):\n                    if ind == i:\n                        continue\n                    if prev_max < dp[i][il]:\n                        break\n                    else:\n                        dp[i][il] = max(dp[i][il], min(dif_l[ind], prev_max))\n                tmp = [v[0] for v in pq_l[il]]\n                ind = bisect.bisect_right(tmp, dp[i][il])\n                pq_l[il].insert(ind, [dp[i][il], i])\n                \n            il = 1\n            tmp = [v[0] for v in pq_l[il]]\n            ind = bisect.bisect_right(tmp, dp[i][il])\n            pq_l[il].insert(ind, [dp[i][il], i])\n            \n            # print(i, pq_l, dif_l)\n                        \n                \n                # dp[i][1] = max(dp[i][1], dif)\n                # for il in range(2,l):\n                #     if dp[j][il-1] == -1:\n                #         break\n                #     dp[i][il] = max(dp[i][il], min(dif, dp[j][il-1]))\n            ans = max(ans, dp[i][-1])\n    #     print(dp)\n    # print(dic)\n    print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14465