Maximize the Minimum

Wednesday, March 30, 2022

JJ has an array

A

of size

N

. He can perform the following operations on the array at most

K

times:

Set $A_{i} := A_{i + 1}$

where

1 \leq i \leq N - 1

Set

A_{i} := A_{i - 1}

where

2 \leq i \leq N

He wants to maximize the value of the minimum element of the array $A$

. Formally, he wants to maximize the value of

min_{1 \leq i \leq N} A_{i}

Can you help him do so?

Input Format

The first line contains a single integer $T$

- the number of test cases. Then the test cases follow.

The first line of each test case contains two integers

N

and

K

- the size of the array

A

and the maximum number of operations allowed respectively.

The second line of each test case contains

N

space-separated integers

A_{1}, A_{2}, \dots, A_{N}

denoting the array

A

Output Format

For each test case, output the maximum value of the minimum element of the array $A$

that can be obtained after applying the given operation at most

K

times.

Constraints

$1 \leq T \leq 100$

2 \leq N \leq 10^{5}

0 \leq K \leq 10^{5}

1 \leq A_{i} \leq 10^{9}

Sum of

N

over all test cases does not exceed

2 \cdot 10^{5}

Sample Input 1

4
5 4
5 4 3 2 1
6 1
8 2 3 9 6 10
5 2
4 3 4 3 5
5 1000
4 3 4 3 5

Sample Output 1

Explanation

Test Case 1: We can perform the following operations (in the following order):

Set $A_{2} := A_{1}$

. Array

A

becomes

[5, 5, 3, 2, 1]

Set

A_{3} := A_{2}

. Array

A

becomes

[5, 5, 5, 2, 1]

Set

A_{4} := A_{3}

. Array

A

becomes

[5, 5, 5, 5, 1]

Set

A_{5} := A_{4}

. Array

A

becomes

[5, 5, 5, 5, 5]

Therefore the answer is $5$

Test Case 2: We can perform the following operations (in the following order):

Set $A_{2} := A_{3}$

. Array

A

becomes

[8, 3, 3, 9, 6, 10]

Therefore the answer is $3$

Test Case 3: We can perform the following operations (in the following order):

Set $A_{2} := A_{3}$

. Array

A

becomes

[4, 4, 4, 3, 5]

Set

A_{4} := A_{3}

. Array

A

becomes

[4, 4, 4, 4, 5]

Therefore the answer is $4$

Search This Blog

Coders