human
Solve in Python:
You and your $n - 1$ friends have found an array of integers $a_1, a_2, \dots, a_n$. You have decided to share it in the following way: All $n$ of you stand in a line in a particular order. Each minute, the person at the front of the line chooses either the first or the last element of the array, removes it, and keeps it for himself. He then gets out of line, and the next person in line continues the process.

You are standing in the $m$-th position in the line. Before the process starts, you may choose up to $k$ different people in the line, and persuade them to always take either the first or the last element in the array on their turn (for each person his own choice, not necessarily equal for all people), no matter what the elements themselves are. Once the process starts, you cannot persuade any more people, and you cannot change the choices for the people you already persuaded.

Suppose that you're doing your choices optimally. What is the greatest integer $x$ such that, no matter what are the choices of the friends you didn't choose to control, the element you will take from the array will be greater than or equal to $x$?

Please note that the friends you don't control may do their choice arbitrarily, and they will not necessarily take the biggest element available.

-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains three space-separated integers $n$, $m$ and $k$ ($1 \le m \le n \le 3500$, $0 \le k \le n - 1$)  — the number of elements in the array, your position in line and the number of people whose choices you can fix.

The second line of each test case contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)  — elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3500$.

-----Output-----

For each test case, print the largest integer $x$ such...

What is a Python program to print the largest integer $x$ such?
assistant
#Here is Python program to print the largest integer $x$ such.

import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx =...