Description：

给定一个长为 $n$ 的序列 $a_i$ ，你可以执行任意次操作，每次操作可以交换 两个相邻位置 $(i,i+ 1)$ 上的数，且交换后位置上的数变为 $(a_{i+1}+1,a_i−1)$ ，问是否能通过任意次操作使得 $a_i$ 不降，若有解则给出最终的 $a_i$ 。

$1\le n \le 2\times10^5$

Solution：

设 $x,y$ 被调到了 $u,v(u < v)$ ，则有 $a_x+(x-u)\le a_y+(y-v)$ ，即 $a_x+x\le a_y+y+(u-v)$ ，因为 $u<v$ ，所以 $a_x+x<a_y+y$ ，所以将所有数按 $a_i+i$ 排序就得到了最后的答案，然后模拟就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

int a[MAXN];

int s[MAXN];

bool cmp(int x,int y){return a[x] + x < a[y] + y;}

int b[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp);

	for(int i = 1;i <= n;++i)b[i] = a[s[i]] + s[i] - i;

	bool found = true;

	for(int i = 1;i < n;++i)if(b[i] > b[i + 1]){found = false;break;}

	if(found)for(int i = 1;i <= n;++i)cout << b[i] << " ";

	else cout << ":(";

	cout << endl;

	return 0;

}