问题描述

整数 $v$ 是长度为 $m$ 的数组 $b$ 的中值，当且仅当：

• $v$ 大于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素，且
• $v$ 小于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素。

例如

• $[9, 3, 7]$ 的唯一中值是 $7$ 、
• $[5, 3, 7, 9]$ 的中值是 $5$ 、 $6$ 和 $7$ ，以及
• $[2, 2, 2]$ 的唯一中值是 $2$ 。

给你一个整数 $k$ 和一个数组 $a_1, \ldots, a_n$ ，数组中的整数介于 $1$ 和 $n$ 之间。

从 $1$ 到 $n$ 之间的整数 $v$ 如果存在至少一对索引 $(l, r)$ 且满足以下条件，则称该整数 $v$ 为子中值

• $1 \leq l \leq r \leq n$ ,
• $r - l + 1 \geq k$ ,
• $v$ 是子数组 $[a_l, \ldots, a_r]$ 的中值。

可以证明总是存在至少一个子中值。请找出最大的子中值 $v_{max}$ 。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 50\,000$ )。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \leq k \leq n \leq 300\,000$ )。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq n$ )。

保证所有测试用例中 $n$ 的总和不超过 $300\,000$ 。

输出格式

对于每个测试用例，输出一个整数最大子中值 $v_{max}$。

样例输入

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

样例输出

4
3
2
3
1
2
3