Just do it

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

#define int long long
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int median(int a, int b, int c)
{
    int m1 = min(a, b), m2 = min(a, c), m3 = min(b, c);
    int ret = max(max(m1, m2), m3);
    return ret;
}

int HiitSort(vi& array, int low, int high)
{
    if(high - low <= 1)
        return 0;
    int ret = 0, pivot = median(array[low], array[(low+high)/2], array[high-1]);
    int a = low, b = high - 1;
    while(true)
    {
        while(array[a] < pivot) {
            a++, ret++;
        }
        while(array[b] > pivot) {
            b--, ret++;
        }
        if(a >= b)
            break;
        swap(array[a], array[b]);
        a++, b--;
    }
    ret += HiitSort(array, low, a);
    ret += HiitSort(array, a, high);
    return ret;
}


int cur;
void Put(vi& v, int l, int r)
{
    int m = (l+r) / 2;
    if(!v[m])
        v[m] = cur--;

    if(r - l > 1) {
        Put(v, m, r);
        Put(v, l, m);
    }
}

signed main() {
#ifdef LOCAL
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
#endif
    int n;
    cin >> n;

    vi test(n, 0);
    test[0] = 1, test[n-1] = n;
    cur = n - 1;
    Put(test, 0, n);
    // for(int x: test)
    //     cout << x << " ";
    // cout << endl;

    // vi array = test;
    // int times = HiitSort(array, 0, n);
    // cerr << times << " " << the << endl;

    int the = n*n / 4, times;
    bool flag = true;
    while(flag)
    {
        vi array = test;
        times = HiitSort(array, 0, n);
        if(times > the)
        {
            cerr << times << " " << the << endl;
            for(int x: test)
                cout << x << " ";
            return 0;
        }
        next_permutation(all(test));
    }

    return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

3 2

Test 3

Verdict: ACCEPTED

5 4

Test 4

Verdict: ACCEPTED

7 6

Test 5

Verdict: ACCEPTED

10 9

Test 6

Verdict: ACCEPTED

13 12

Test 7

Verdict: ACCEPTED

17 16

Test 8

Verdict: ACCEPTED

21 20

Test 9

Verdict: ACCEPTED

26 25

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: TIME LIMIT EXCEEDED