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;


inline int median(const int& a, const int& b, const 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;
}


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

    vi test(n, 0);
    // for(int i = 0; i<n; i++)
    //     test[i] = i+1;
    if( n <= 5)
    {
        for(int i=0; i<n; i++)
            test[i] = i+1;
        int the = n*n / 4, times;
        bool flag = true;
        while(flag)
        {
            vi array = test;
            times = HiitSort(array, 0, n);
            if(times >= the)
            {
                for(int x: test)
                    cout << x << " ";
                cout << endl;
                // the = times;
                return 0;
            }
            next_permutation(all(test));
        }
    } else {
        test[n/2] = n;
        test[n/2 - 1] = 1;

        for(int i = 0; i < n/2 - 1; i++)
            test[i] = i+2;
        for(int i = n/2 + 1; i < n; i++)
            test[i] = i;
        for(int x: test)
            cout << x << " ";
    }
    
    // int the = n*n / 4, times;
    // vi array = test;
    // times = HiitSort(array, 0, n);
    // cerr << (times > the) << ' ' << times << ' ' << the;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED