Description：

给出一个字符串的 $sa$ 数组还原字符串。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

贪心，枚举字典序相邻的两个后缀 $p1$ 和 $p2$ ，通过 $rnk$ 比较一下后缀 $p1+1$ 和 $p2+1$ ，如果他们已经符合顺序，那么这两个位置字符就可以相同，否则的话 $p2$ 必须大于 $p1$ ，最后判断一下字符数是否超过 $26$ 个即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

int sa[MAXN],rnk[MAXN];

char c[MAXN];

int main()

{

	scanf("%d",&n);

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

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

	int cur = 'a';

	c[sa[1]] = cur;

	for(int i = 1;i < n;++i)

	{

		int p1 = sa[i],p2 = sa[i + 1];

		if(rnk[p1 + 1] < rnk[p2 + 1])c[sa[i + 1]] = cur;

		else c[sa[i + 1]] = ++cur;

	}

	if(cur > 'z')puts("-1");

	else for(int i = 1;i <= n;++i)putchar(c[i]);

	return 0;

}