Recover the Lexicographically Smallest String

For a string \(s\) of length \(n\), we define \(p_j = x\) if the suffix \(s[x \ldots j]\) is the minimum suffix among all suffixes of \(s[1\ldots j]\) (i.e. it is lexicographically smaller than every other suffix of \(s[1\ldots j]\)). Note that a suffix \(t\) is considered lexicographically smaller than another suffix \(u\) if either \(t\) is a prefix of \(u\) (and \(t \neq u\)) or there exists an index \(k\) such that \(t_i=u_i\) for \(i=1,\ldots, k-1\) and \(t_k < u_k\).

You are given the sequence \(p_1, p_2, \ldots, p_n\) from an unknown string \(s\). It turns out that for any valid string \(s\), if we require \(s\) to be lexicographically smallest among all possibilities then its structure is forced. In fact, one may prove that under the lexicographically smallest condition the following holds:

• \(s_1 = a\).
• For every \(j \ge 2\), we have \(p_j = j\) if and only if \(s_j = a\); otherwise, when \(s_j \ne a\) (and note that \(s_1=a\) is the smallest letter available) the minimum suffix of \(s[1\ldots j]\) starts at index 1, so \(p_j = 1\).

Your task is to recover \(s\) given \(p_1, p_2, \ldots, p_n\). If the input \(p\)-sequence is valid then the answer is unique. In summary, if \(p_1,p_2,\ldots,p_n\) is provided, the lexicographically smallest solution is the string \(s\) defined as:

[ s_1 = a, \quad \text{and for } j \ge 2,; s_j = \begin{cases} a &\text{if } p_j=j,\ b &\text{if } p_j=1. \end{cases} ]

You may assume that the input is valid; that is, for every \(j\), \(p_j\) is either 1 or \(j\), and \(p_1=1\).

inputFormat

The first line contains an integer \(n\) (1 \(\le n \le\) 10⁵), the length of the string.

The second line contains \(n\) space‐separated integers \(p_1, p_2, \ldots, p_n\). It is guaranteed that \(p_1=1\) and for every \(j \ge 2\), \(p_j\) is either 1 or \(j\).

outputFormat

Output the recovered string \(s\) of length \(n\), which is guaranteed to be unique and lexicographically smallest.

sample

1
a
1

a