Code : Med-imize

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e6;

// Assumption : a contains only -1 and 1.
// A good subsequence is one where there are a multiple of k elements in
// between any 2 elements.
int max_good_subseq_sum_of_size_r(vector<int> a, int k, int req_len) {
    int n = a.size();

    // dp[i][j] is the maximum sum good subsequence of length j ending at an
    // index i.
    vector<vector<int>> dp(n, vector<int>(req_len + 1, -inf));

    for (int i = 0; i < n; i++) {
        vector<int> ndp = dp[i];

        // A subsequence can only start at i if the re are a multiple of k
        // elements to the left.
        if (i % k == 0) {
            ndp[1] = a[i];
        }

        int m = (i - 1 + k) % k;
        for (int s = i - 1; s >= 0; s--) {
            if (s % k == m) {
                for (int len = 1; len < req_len; len++) {
                    ndp[len + 1] = max(ndp[len + 1], dp[s][len] + a[i]);
                }
            }
        }

        swap(dp[i], ndp);
    }

    // Indices modulo k is 0, 1, 2, 3, ... r - 1.
    int res = -1;
    for (int i = 0; i < n; i++) {
        if (i % k == req_len - 1) {
            res = max(res, dp[i][req_len]);
        }
    }
    return res;
}

void solve(vector<int> &a, int k) {
    int n = a.size();

    int r = n % k;
    if (r == 0) {
        r = k;
    }

    int low = *min_element(a.begin(), a.end());
    int high = *max_element(a.begin(), a.end());
    int res = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        vector<int> temp = a;
        for (auto &ele : temp) {
            ele = (ele >= mid ? 1 : -1);
        }

        int median = max_good_subseq_sum_of_size_r(temp, k, r);
        if (median > 0) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, k);
    }
}

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e6;

// Assumption : a contains only -1 and 1.
// A good subsequence is one where there are a multiple of k elements in
// between any 2 elements.
int max_good_subseq_sum_of_size_r(vector<int> a, int k, int req_len) {
    int n = a.size();

    // dp[m][j] is the maximum sum good subsequence of length j ending at an
    // index with modulo m.
    vector<vector<int>> dp(k, vector<int>(req_len + 1, -inf));

    for (int i = 0; i < n; i++) {
        vector<int> ndp = dp[i % k];

        // A subsequence can only start at i if the re are a multiple of k
        // elements to the left.
        if (i % k == 0) {
            ndp[1] = max(ndp[1], a[i]);
        }

        int m = (i - 1 + k) % k;
        for (int len = 1; len < req_len; len++) {
            ndp[len + 1] = max(ndp[len + 1], dp[m][len] + a[i]);
        }

        swap(dp[i % k], ndp);
    }

    // Indices modulo k is 0, 1, 2, 3, ... r - 1.
    int res = dp[req_len - 1][req_len];
    return res;
}

void solve(vector<int> &a, int k) {
    int n = a.size();

    int r = n % k;
    if (r == 0) {
        r = k;
    }

    int low = *min_element(a.begin(), a.end());
    int high = *max_element(a.begin(), a.end());
    int res = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        vector<int> temp = a;
        for (auto &ele : temp) {
            ele = (ele >= mid ? 1 : -1);
        }

        int median = max_good_subseq_sum_of_size_r(temp, k, r);
        if (median > 0) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, k);
    }
}

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e6;

// Assumption : a contains only -1 and 1.
// A good subsequence is one where there are a multiple of k elements in
// between any 2 elements.
int max_good_subseq_sum_of_size_r(vector<int> a, int k, int req_len) {
    int n = a.size();

    vector<int> dp(k + 1, -inf);
    // dp[len] is the maximum sum of a good subsequences of length len.
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        // If the subsequence ends at i, then its length is predetermined.
        // There are i elements to the left. From these elements, you
        // need to remove blocks of size k.
        int prev_cnt = i;
        int len = 1 + prev_cnt % k;
        dp[len] = max(dp[len], dp[len - 1] + a[i]);
    }

    return dp[req_len];
}

void solve(vector<int> &a, int k) {
    int n = a.size();
    if (k > n) {
        k = n + 1;
    }

    int r = n % k;
    if (r == 0) {
        r = k;
    }

    int low = *min_element(a.begin(), a.end());
    int high = *max_element(a.begin(), a.end());
    int res = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        vector<int> temp = a;
        for (auto &ele : temp) {
            ele = (ele >= mid ? 1 : -1);
        }

        int median = max_good_subseq_sum_of_size_r(temp, k, r);
        if (median > 0) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a, k);
    }
}