Binary Deletion - Repovive Goodbye 2025 Round | Repovive

1B. Binary Deletion

1000 pts2s256 MB

You are given an array $a_1,a_2,\ldots,a_n$ .

You may apply the following operations to the array:

Choose two consecutive elements and delete the left one.
Choose two consecutive elements and delete the right one.

After performing exactly $n-1$ operations, only one element remains.

You must perform operation 1 exactly $k$ times, and operation 2 exactly $n-1-k$ times.

Among all valid sequences of operations, determine the maximum possible value of the final remaining element.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$0 \le k \le n-1$
$1 \le a_i \le n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t \\[0.5em] \left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

5 0
3 1 4 1 5

Case 2

5 4
3 1 4 1 5

Case 3

5 2
3 1 4 1 5

Case 4

1 0
42

Explanation

Case 1

$n=5$ , $k=0$ , $a=[3, 1, 4, 1, 5]$

With $k=0$ , we only use operation 2 (delete right). This forces us to always delete rightward, so only $a_1=3$ can survive. Answer: 3.

Case 2

$n=5$ , $k=4$ , $a=[3, 1, 4, 1, 5]$

With $k=n-1=4$ , we only use operation 1 (delete left). This forces us to always delete leftward, so only $a_5=5$ can survive. Answer: 5.

Output

Case 1

Case 2

Case 3

Case 4

You are given an array $a_1,a_2,\ldots,a_n$ .

You may apply the following operations to the array:

Choose two consecutive elements and delete the left one.
Choose two consecutive elements and delete the right one.

After performing exactly $n-1$ operations, only one element remains.

You must perform operation 1 exactly $k$ times, and operation 2 exactly $n-1-k$ times.

Among all valid sequences of operations, determine the maximum possible value of the final remaining element.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$0 \le k \le n-1$
$1 \le a_i \le n$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t \\[0.5em] \left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

$n=5$ , $k=0$ , $a=[3, 1, 4, 1, 5]$

With $k=0$ , we only use operation 2 (delete right). This forces us to always delete rightward, so only $a_1=3$ can survive. Answer: 3.

$n=5$ , $k=4$ , $a=[3, 1, 4, 1, 5]$

With $k=n-1=4$ , we only use operation 1 (delete left). This forces us to always delete leftward, so only $a_5=5$ can survive. Answer: 5.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1B. Binary Deletion

Input

Output

Samples

1B. Binary Deletion

Constraints

Input

Output

Samples

Constraints