# D. Empty Graph

Đề bài : https://codeforces.com/contest/1712/problem/D

Bài này thực sự đã làm khó mình do 2 lý do :
1. Mình nghĩ sai hướng : ban đầu mình không biết xử lý dữ kiện trọng số của cạnh ntn, thế cho nên mình ngồi nghĩ đến cách build đồ thị và xét nó ở th tổng quát, sau vài tiếng suy nghĩ, mình bế tắc và nhận ra đây không phải là cách. Rồi mình bắt đầu chú ý đến tính chất đặc biệt của bài toán là cách tạo trọng số của nó. Sau đó mình rút ra một kết luận rất quan trọng : max diameter luôn <= 2*min(a[1] ... a[n]), dựa vào đây mình rút ra được thuật chặt nhị phân.
2. Bài này khá nhiều test case, mình chỉ ngồi nghĩ mà không ghi ra giấy nên khá rối.

Code :
::: spoiler

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i) 
#define rev(i, a, b) for (int i = (a); i >= (b); --i) 
#define ll long long
#define pii pair<int, int>
#define pli pair<long long, int>
#define pb push_back
#define fi first
#define pii pair<int, int>
#define se second
#define lb long double

using namespace std; 
const int mxn = 2e5 + 5;
const ll MOD = 998244353;
const ll INF = 1e9;
ll a[mxn], temp[mxn];
pli b[mxn];
int L[mxn], R[mxn];
ll res;
int n, k;

void check()
{
    ll dis[4][4];
    rep(i, 1, n) rep(j, 1, n)
    {
        ll mi = INF*4ll;
        rep(k, min(i, j), max(i, j)) mi = min(mi, a[k]);
        dis[i][j] = mi;
    }
    rep(i, 1, n) dis[i][i] = 0;

    rep(k, 1, n) rep(i, 1, n) rep(j, 1, n)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    rep(i, 1, n) rep(j, 1, n)
        res = max(res, dis[i][j]);
}

void dfs(int i, int t)
{
    if (i > n)
    {
        check();
        return;
    }

    dfs(i + 1, t);

    if (t > 0)
    {
        ll old = a[i];
        a[i] = INF;
        dfs(i + 1, t - 1);
        a[i] = old;
    }
}

void cal_LR()
{
    vector<int> vec;
    temp[0] = -1;
    vec.pb(0);

    rep(i, 1, n)
    {
        while(temp[i] <= temp[vec.back()])
            vec.pop_back();
        L[i] = vec.back() + 1;
        vec.pb(i);
    }

    vec.clear();    
    temp[n + 1] = -1;
    vec.pb(n + 1);

    rev(i, n, 1)
    {
        while(temp[i] <= temp[vec.back()])
            vec.pop_back();
        R[i] = vec.back() - 1;
        vec.pb(i);
    }
}

bool exist(ll val)
{
    int t = k;
    ll least = (val + 1)/2;
    rep(i, 1, n) temp[i] = a[i];
    rep(i, 1, n) if (t > 0)
    {
        if (b[i].fi < least)
        {
            --t;
            temp[b[i].se] = INF;
        }
        else break;
    }
    
    if (k - t  + 1 <= n && b[k - t + 1].fi < least) return 0;

    if (t == k)
    {
        if (t >= 2) return 1;
        if (b[n].fi >= val) return 1;
    }

    if (t >= 2) return 1;
    if (t == 1)
    {
        if (b[n].fi >= val) return 1;
        if (k > t) return 1;
        temp[b[k].se] = INF;
    }

    cal_LR();
    rep(i, 1, n) if (temp[i] >= val && R[i] - L[i] > 0)
        return 1;

    return 0;
}

ll solve()
{
    ll l = 1, r = INF*2ll;
    while(l < r)
    {
        ll mid = (l + r + 1)>>1;
        if (exist(mid)) l = mid;
        else r = mid - 1;
    }

    return l;
}

int main(){
    //freopen("H:\\file_txt\\input.txt", "r", stdin);
    //freopen("H:\\file_txt\\output.txt", "w", stdout);

    int t; cin >> t;
    while(t--)
    {
        scanf("%d%d", &n, &k);
        rep(i, 1, n) 
        {
            scanf("%lli", &a[i]);
            b[i] = {a[i], i};
        }
        sort(b + 1, b + n + 1);

        res = -1;
        if (n <= 3) 
        {
            res = -1;
            dfs(1, k);
            printf("%lli\n", min(INF, res));
        }
        else
            printf("%lli\n", min(INF, solve()));
        /*cout << exist(7) << endl;
        rep(i, 1, n) cout << L[i] << ' '; cout << endl;
        rep(i, 1, n) cout << R[i] << ' ';*/
    }
}

:::