D - suffix array Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はsuffix arrayの構築アルゴリズムが大好きです。毎日さまざまなsuffix arrayの構築アルゴリズムを実装して遊んでいます。 しかし、高橋君はsuffix arrayを構築しすぎてしまったので、suffix arrayを構築するのに飽きてしまいました。 そこで高橋君は、与えられた順列に対し、その順列をsuffix arrayに持つような辞書順最小の文字列を求めることにしました。

ただし、2つの文字列X_1,X_2,...,X_sとY_1,Y_2,...,Y_tに対し、辞書順でX<Yとは、以下のいずれか片方の条件を満たすこととします。

  • ある整数i(1 ≦ i ≦ min(s,t))が存在し、1 ≦ j ≦ i-1を満たす任意の整数jに対してX_j=Y_jで、かつX_i<Y_i
  • 任意の整数i(1 ≦ i ≦ min(s,t))に対してX_i=Y_iで、かつs<t

また、与えられた文字列Sに対し、そのsuffix arrayとは、すべてのiに対して、Sのi文字目から末尾までを順に並べた文字列を列挙し、その文字列たちを辞書順に並び替えた列の各要素に対し、対応するiを順に並べたものです。 たとえば、文字列ABACABAのsuffix arrayは[7,5,1,3,6,2,4]となります。

長さNの順列が与えられるので、その順列をsuffix arrayに持つ英大文字のみからなる辞書順最小の文字列を求めてください。そのような文字列が存在しなければ、代わりに-1を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N
  • 1 行目には、整数N(1 ≦ N ≦ 10^6)が与えられる。
  • 2 行目には、整数列A_1,...,A_N(1 ≦ A_1,...,A_N ≦ N)が与えられる。これらN個の整数はどの2つも互いに異なることが保障される。

出力

順列A_1,...,A_Nをsuffix arrayに持つ辞書順最小の文字列を出力せよ。

出力の末尾に改行を入れること。(21:40修正)

入力例1

7
7 5 1 3 6 2 4

出力例1

ABACABA

条件を満たす文字列は他にもCXHZBWAなどがありますが、辞書順最小のABACABAを出力します。

入力例2

12
7 1 9 10 2 4 3 6 12 5 11 8

出力例2

BDEDGFAHCCGG