问题描述

给定一个长度为 $N$ 的序列 $a$。

第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。

第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。

第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。

第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。

输入格式

第一行输入一个正整数 $N$。$(1\le N\le 2\times 10^5)$

第二行输入 $N$ 个正整数，表示序列 $a$。$(1\le a_i\le 10^5,1\le i\le N)$

输出格式

第一行输出每个数字其左边第一个比其大的数字，不存在则输出 -1。

第二行输出每个数字其右边第一个比其大的数字，不存在则输出 -1。

第三行输出每个数字其左边第一个比其小的数字，不存在则输出 -1。

第四行输出每个数字其右边第一个比其小的数字，不存在则输出 -1。

样例输入

5
4 3 2 1 5

样例输出

-1 4 3 2 -1
5 5 5 5 -1
-1 -1 -1 -1 1
3 2 1 -1 -1