Hello Codeforces community!I would like to share an intuitive approach to solve the problem where we need to construct a permutation of length [3n]⁠ such that the sum of medians of [n]⁠ contiguous blocks (each of size 3) is maximized.

Method ExplanationTo maximize the sum of the medians, we want the median of each triplet to be as large as possible.Let's think greedily. A median of 3 elements only requires one element smaller than it and one element larger than it. Therefore, to save the largest possible numbers to become medians, we should sacrifice the smallest [n]⁠ numbers (from [1]⁠ to [n]⁠) to be the "left elements" (the smallest element in each triplet).

For the remaining [2n]⁠ larger numbers (from (n+1) to [3n]⁠), we can pair them up sequentially. For each block [i]⁠ (from [1]⁠ to [n]⁠):Left element: [i]⁠Median element: (n + 2i — 1)Right element: (n + 2i)When sorted, the triplet ((i, n + 2i — 1, n + 2i)) will always have (n + 2i — 1) as its median. This perfect construction utilizes the largest numbers effectively.

And here is the typical code for this problem

include <bits/stdc++.h>

using namespace std;

using ll = long long;

void solve(){

ll n;

cin >> n;

vector<ll>permutation;

permutation.reserve(3 * n);

for(int i = 1; i <= n; i++){

    ll left = i;

    ll median = n + 2 * i - 1;

    ll right = n + 2 * i;

    permutation.push_back(left);
    permutation.push_back(median);
    permutation.push_back(right);
}
for(int i = 0; i < 3 * n; i++){
    cout << permutation[i] << (i == 3 * n - 1 ? "" : " ");
}
cout << "\n";

}

signed main() {

ios_base::sync_with_stdio(0);
cin.tie(0);

ll t;
cin >> t;

while(t--) solve();
return 0;

}