Description

求 $pre[i]$  和 $suf[i]$。

$pre[i]$ 表示 $\forall\ a_j<a_i(j<i),j≤pre[i]$。

$suf[i]$ 表示 $\forall\ a_j>a_i(j>i),j≥suf[i]$。

注：$pre[i]=0$，$suf[i]=n+1$。

Input Format

第一行一个整数 $n$ 表示序列大小。

第二行 $n$ 个整数表示 $a_i$。

Output Format

第一行 $n$ 个整数表示 $pre[i]$。

第二行 $n$ 个整数表示 $suf[i]$。

6
1 2 3 4 5 6

0 1 2 3 4 5 
2 3 4 5 6 7

Hint

$1≤n≤10^6,1≤a_i≤10^9$

Source

模板