Seta は CCO のための問題を作成しています！彼女は次のような問題を思いつきました。
値が範囲 $[1, N]$ にある配列 $A[1, \dots, N]$ が与えられたとき、$B[i]$ を $\ell \le i \le r$ かつ $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r])$$ を満たす組 $(\ell, r)$ の個数と定義します。
配列 $B[1, \dots, N]$ を出力してください。
しかし、CCO の前日に Seta のコンピュータがクラッシュしてしまい、彼女は出力ファイルしか復元できませんでした。出力された配列 $B[1, \dots, N]$ が与えられたとき、入力配列 $A[1, \dots, N]$ を復元するプログラムを書くことができますか？
Seta は、配列 $A$ は一意とは限らず、有効な配列であればどれでも受け入れると念を押しています。
入力
入力の最初の行には整数 $N$ が含まれます。2 行目には $N$ 個の空白区切りの整数 $B[1], \dots, B[N]$ ($1 \le B[i] \le N^2$) が含まれます。
以下の表は、25 点分の配点の内訳を示しています。
| 配点 | $N$ の範囲 | 追加制約 |
|---|---|---|
| 2 点 | $1 \le N \le 8$ | なし |
| 3 点 | $1 \le N \le 5000$ | 元の配列 $A$ は順列である |
| 5 点 | $1 \le N \le 3 \times 10^5$ | 元の配列 $A$ は順列である |
| 5 点 | $1 \le N \le 3 \times 10^5$ | なし |
| 5 点 | $1 \le N \le 5 \times 10^6$ | 元の配列 $A$ は順列である |
| 5 点 | $1 \le N \le 5 \times 10^6$ | なし |
出力
$N$ 個の空白区切りの整数、すなわち配列 $A[1], \dots, A[N]$ を出力してください。ここで $1 \le A[i] \le N$ です。少なくとも 1 つの有効な配列 $A$ が存在することが保証されています。
有効な配列が複数存在する場合、どの有効な配列を出力しても構いません。特に、元の配列 $A$ が順列であったとしても、あなたの回答は順列である必要はありません。
入出力例
入力 1
3 3 1 2
出力 1
1 3 2
注記 1
- 部分配列 $[1, 3, 2], [1, 3], [1]$ の最小値は 1 です。このような部分配列は 3 つあります。
- 部分配列 $[3]$ の最小値は 3 です。このような部分配列は 1 つあります。
- 部分配列 $[3, 2]$ と $[2]$ の最小値は 2 です。このような部分配列は 2 つあります。
入力 2
2 2 2
出力 2
1 1
入力 3
3 1 4 1
出力 3
2 1 3
注記 3
$A = [2, 1, 2]$ も判定において受け入れられることに注意してください。