#include<bits/stdc++.h>
#include"partition.h"
using namespace std;
vector<int> solve(vector<int> a){
    int n=a.size();
    vector<int> ret;
    a.push_back(-1);
    sort(a.begin(),a.end());
    int P,I;
    P=I=0;
    for(int i=1;i<=n;i++){
        if(i%2==1) I+=a[i];
        else P+=a[i];
    }
    if(P<=I){
        for(int i=1;i<=n;i++){
            if(i%2==0) ret.push_back(a[i]);
        }
        for(int i=n;i;i--){
            if(i%2==1) ret.push_back(a[i]);
        }
        return ret;
    }
    else{
        vector<int> difs;
        if(n%2==1) a.push_back(1e9+1);
        for(int i=1;i<=n;i+=2){
            difs.push_back(a[i+1]-a[i]);
        }
        while(P>I&&*max_element(difs.begin(),difs.end())!=-1){
            int idx=0;
            for(int i=1;i<difs.size();i++){
                if(difs[idx]>difs[i]&&difs[i]!=-1) idx=i;
            }
            P-=difs[idx];
            I+=difs[idx];
            difs[idx]=-1;
            swap(a[2*idx+1],a[2*idx+2]);
        }
        vector<int> ret,pp,ip;
        for(int i=1;i<=n;i++){
            if(i%2==0) pp.push_back(a[i]);
            else ip.push_back(a[i]);
        }
        sort(pp.begin(),pp.end());
        sort(ip.begin(),ip.end(),greater<int>());
        for(auto x:pp) ret.push_back(x);
        for(auto x:ip) ret.push_back(x);
        return ret;
    }
}