题目描述

请注意此题时间限制

小明学会LIS算法以后，开始学习KMP。

有一天，他终于理解了$next$数组的含义了：

给定一个只包含小写字母的字符串$s$，下标从$1$开始编号，$next[i](next[i]<i)$表示的是最大的符合条件的位置，满足：$s_{[1,next[i]]}=s_{[|s|-next[i]+1,i]}$，如果不存在这样的数字，则$next[i]=0$。

例如，字符串$abcabcaa$，$next$数组为：$[0,0,0,1,2,3,4,1]$。

然而他又把原字符串弄丢了（为什么要说又？），请你帮他恢复一下原字符串长什么样，如果有多解，输出字典序最小的那一个。

输入格式

第一行输入$n$，接下来一行输入$n$个数字表示$next$数组。

输出格式

输出一个长度为$n$的字符串，保证有解。

样例输入1

8
0 0 0 1 2 3 4 1

样例输出1

abbabbaa

下发文件

数据范围

对于20%的数据：$n\leq 7$。

对于40%的数据：$n\leq 1000$。

对于100%的数据：$2\leq n\leq 2\times 10^5$。