解题思路

给定长度为 n 的数组 $a_1,\dots,a_n$ 。要求构造只含小写字母的字符串 $s_1\dots s_n$ ，并满足：

若 $a_i=0$ ： $s_i$ 必须是一个从未出现过的新字符；
若 $a_i>0$ ：有 $1\le a_i<i$ 且 $s_i=s_{a_i}$ ，并且在区间 $(a_i,i)$ 内没有与 $s_{a_i}$ 相同的字符（即 $a_i$ 正是该字符在 $i$ 之前的“上一次出现位置”）。

由题意保证数据合法且所需不同字符数不超过 26。

核心思路（贪心/直接构造）：

题目内容

给定一个长度为 $n$ 的数组 { $a_1,a_2,...,a_n$ } 。请你构造一个长度为 $n$ 、仅由小写字母构成的字符串 $s$ ，满足对每一个位置 $i(1≤i≤n)$ ：

若 $a_i=0$ ，则 $s_i$ 在位置 $[1,i-1]$ 中从未出现过；

若 $a_i＞0$ ，则 $1≤a_i＜i$ ,并且 $s_i=s_{a_i}$ ，同时在所有 $a_i＜j＜i$ 的位置上均满足 $s_j≠s_{a_i}$ （即 $a_i$ 的确是 $s_i$ 的上一个出现位置）。

换言之， $a_i$ 给出了 $s_i$ 的“上一个相同字符的位置”（若不存在则为 $0$ ）。保证输入一定合法，即存在至少一个满足条件的子符串。

第一行输入一个整数 $n(1≤n≤2×10^5)$ 表示字符串长度。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(0≤a_i＜i)$ 表示数组 $a$ 。并保证所有 $a_i$ 构成若干条严格指向更小下标的“链”，从而对应某个可行字符串。

除此之外，保证输入的数据满足：存在一个仅由小写英文字母构成的解（即构造所需的独立字符数量不超过 $26$ ）

输出一行，一个长度为 $n$ 的字符串 $s$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

输入

10
0 0 1 2 0 5 3 7 0 9

输出

ababccaadd

说明

设输出字符串 $s="ababccaadd"$ ，对应关系如下（下标从 $1$ 开始）：

逐一核对可知， $a_i$ 确为 $s_i$ 的上一次出现位置（无则为 $0$ ），满足题意。