记录编号	602292	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	1.736 s
提交时间	2025-07-03 15:12:49	内存使用	16.06 MiB

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

ll n,x,ousx,jisx;
ll a[1100000],b[1100000];
ll ous[1100000],jis[1100000],cnt1,cnt2;
ll C[1100000];

void a1(ll x,ll y){
	for(;x<=n;x+=(x&-x)) C[x]+=y;
	return;
}

ll a2(ll x){
	ll cnt=0;
	for(;x>0;x-=(x&-x)) cnt+=C[x];
	return cnt;
}

ll a3(ll *z,ll ct){
	ll ans=0;
	for(int i=1;i<=ct;i++){
		ans+=i-1-a2(z[i]);
		a1(z[i],1);
	}
	for(int i=1;i<=ct;i++) a1(z[i],-1);
	return ans;
}

int main() {
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for (int i=1;i<=n;i++) {
        if (i&1) jis[++cnt2]=a[i];
        else ous[++cnt1]=a[i];
    }
    bool check=0;
    if ((a3(ous,cnt1)&1)!=(a3(jis,cnt2)&1)) check=1;
    sort(ous+1,ous+cnt1+1);
    sort(jis+1,jis+cnt2+1);
    for (int i=1;i<=n;i++) {
        if (i&1) b[i]=jis[++jisx];
        else b[i]=ous[++ousx];
    }
    if (check) swap(b[n],b[n-2]);
    for (int i=1;i<=n;i++) {
        cout<<b[i]<<" ";
    }
    return 0;
}