记录编号	602275	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	1.582 s
提交时间	2025-07-03 13:06:21	内存使用	8.41 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+10;
inline void read(int &a){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	a=x*f;return;
}
int n,a[N],b[N],c[N],ta,tb,C[N];
void add(int x,int y){
	for(;x<=n;x+=(x&-x))C[x]+=y;
	return;
}
int ask(int x){
	int cnt=0;
	for(;x>0;x-=(x&-x))cnt+=C[x];
	return cnt;
}
int calc(int *v,int len){
	int ans=0;
	for(int i=1;i<=len;i++){
		ans+=i-1-ask(v[i]);
		add(v[i],1);
	}
	for(int i=1;i<=len;i++)add(v[i],-1);
	return ans;
}
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	read(n);
	for(int i=1,x;i<=n;i++){
		read(x);
		if(i&1)a[++ta]=x;
		else b[++tb]=x;
	}
	if((calc(a,ta)&1)==(calc(b,tb)&1)){
		sort(a+1,a+1+ta);
		sort(b+1,b+1+tb);
		for(int i=1;i<=ta;i++)c[i*2-1]=a[i];
		for(int i=1;i<=tb;i++)c[i*2]=b[i];
		for(int i=1;i<=n;i++)printf("%d ",c[i]);
	}else{
		sort(a+1,a+1+ta);
		sort(b+1,b+1+tb);
		for(int i=1;i<=ta;i++)c[i*2-1]=a[i];
		for(int i=1;i<=tb;i++)c[i*2]=b[i];swap(c[n],c[n-2]);
		for(int i=1;i<=n;i++)printf("%d ",c[i]);
	}
	return 0;
}