4243. KMP

【题目背景】

SAI社的Giftia记忆数据系统中，每台Giftia的核心记忆序列会生成对应的「记忆关联索引数组」（对应KMP的next数组）。某次量子记忆扰动事故后，一台Giftia的核心记忆字符串丢失，仅残留了该「记忆关联索引数组」。你需要根据这份残留的数组，还原出唯一的核心记忆字符串。

【题目描述】

给定一个长度为 $n$ 的整数序列 $idx[1 \dots n]$（记忆关联索引数组），其中 $idx[i]$ 表示Giftia核心记忆字符串 $S$ 的前 $i$ 个字符构成的记忆片段中，最长的相等真前后缀的长度（即记忆片段的重复关联程度，对应标准KMP的next数组定义）。

任务：

1. 构造一个长度为 $n$ 的小写字母字符串 $S$（Giftia的核心记忆字符串），使其记忆关联索引数组恰好为给定的序列；

2. 在满足上述条件的前提下，要求 $S$ 的字典序最小（保证记忆数据的基础排序符合SAI社的存储规范）；

3. 如果给定的序列本身是不合法的（不存在任何记忆字符串能生成这个索引数组），输出 Impossible（表示该Giftia的记忆数据已无法还原）。

【输入格式】

第一行输入一个整数 $n$，表示记忆关联索引数组的长度；

第二行输入 $n$ 个整数，依次为 $idx[1], idx[2], \dots, idx[n]$。

【输出格式】

若给定的 $idx$ 数组合法，输出一行仅包含小写字母的字符串 $S$（字典序最小的Giftia核心记忆字符串）；否则输出一行字符串 Impossible。

【样例输入 1】

5
0 0 1 2 0

【样例输出 1】

ababb

【样例说明 1】

字符串 "ababb" 作为Giftia的核心记忆序列，其记忆关联索引数组为 [0,0,1,2,0]，且是满足条件的字典序最小字符串。

【样例输入 2】

3
0 1 2

【样例输出 2】

aaa

【样例说明 2】

字符串 "aaa" 作为Giftia的核心记忆序列，其记忆关联索引数组为 [0,1,2]，是字典序最小的合法字符串。

【样例输入 3】

4
0 2 1 0

【样例输出 3】

Impossible

【样例说明 3】

不存在任何Giftia核心记忆字符串的记忆关联索引数组为 [0,2,1,0]，因此该Giftia的记忆数据已无法还原，输出 Impossible。

【数据范围】

$1 \le n \le 10^6$

【来源】

To_Carpe_Diem