L. Resonant Purity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of $$$n$$$ integers and a non-negative integer $$$k$$$, find the maximum integer $$$X$$$ such that there exists at least one valid contiguous subarray $$$a[l..r]$$$ satisfying the following conditions :

  • The subarray must contain at least two elements $$$(1 \le l \lt r \le n)$$$.
  • Strictly more than half of the elements in the subarray must be greater than or equal to $$$X$$$.
  • The cost to raise all elements in the subarray to at least $$$X$$$ must not exceed $$$k$$$ i.e. $$$\sum_{i=l}^{r} max(0, X - a_i) \le k$$$.
.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ and $$$k$$$ $$$(0 \le k \le 10^8)$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2 ... a_n$$$ $$$(1 \le a_i \le 10^8)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer $$$X$$$ that is the maximum integer satisfying the problem constraints.

Example
Input
5
3 10
20 20 50
3 50
100 5 100
3 1000
100 1 100
3 100
50 60 10
5 20
100 10 100 10 100
Output
20
55
100
50
30
Note

In the first test case, $$$a=[20,20,50]$$$, $$$k=10$$$. We choose the subarray $$$a[1…2]=[20,20]$$$ with target $$$X=20$$$.

Majority: Elements with value $$$\geq 20$$$ is $$$2$$$. Count is $$$2$$$, Length is $$$2$$$. Since Length $$$ \gt 1$$$ (more than half the subarray length), the condition holds.

Cost: All elements are already $$$\geq 20$$$, the cost is $$$0$$$ which is $$$\le 10$$$. It is impossible to achieve $$$X \gt 20$$$. For example, if $$$X = 21$$$, the only element $$$\geq 21$$$ is $$$50$$$. Any subarray including $$$50$$$ (e.g., $$$[20,50]$$$ or $$$[20,20,50]$$$) would have a majority count of only $$$1$$$, which is not strictly greater than half the length.