#include "bits/stdc++.h"
#include "partition.h"
// #include "grader.cpp"
using namespace std;


#define N 3000005
#define ll long long

const int inf = INT_MAX;

ll n, ans, S = 0;
vector <int> c, a, b, d;

void FF(int x,ll sm,int cnt) {
    if(sm * 2 >= S) {
        int l = cnt;
        int r = n - cnt;
        if(ans > abs(r - l)) {
            a.clear();
            ans = abs(r - l);
            for(int i = 0; i < n; i++) {
                c[i] = b[i];
                if(b[i]) a.push_back(i);
            }
        }
        return;
    }
    if(x == n) return;
    b[x] = 1;
    FF(x + 1, sm + d[x], cnt + 1);
    b[x] = 0;
    FF(x + 1, sm, cnt);
}

vector<int> solve(vector<int> A) {
    // n = (int)A.size();
    // a.clear();
    // c.clear();
    // b.clear();
    // d.clear();
    // S = 0;
    // for(int i = 0; i < n; i++) {
    //     d.push_back(A[i]);
    //     S += A[i];
    //     b.push_back(0);
    //     c.push_back(0);
    // }

    // ans = n + 1;

    // FF(0, 0, 0);
    
    // for(int i = 0; i < n; i++) {
    //     if(!c[i]) a.push_back(i);
    // }
    swap(A[n - 1], A[n / 2]);
    return A;
}