题目描述

这天小明买彩票中了百亿奖金，兴奋的他决定买下蓝桥公司旁的一排连续的楼房。

已知这排楼房一共$N$栋，编号分别为$1～N$，第i栋的高度为$h_i$。

好奇的小明想知道对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个(若不存在则输出-1)。但由于楼房数量太多，小明无法用肉眼直接得到答案，于是他花了1个亿来请你帮他解决问题，你不会拒绝的对吧?

输入描述

第1行输入一个整数$N$， 表示楼房的数量。

第二行输入$N$个整数（相邻整数用空格隔开）, 分别为$h_1, h_2, \ldots,h_N$，表示楼房的高度。

其中$1 \leqslant N \leqslant 7 \times 10 ^ 5， 1 \leqslant h_i \leqslant 10^9$​。

输出描述

输出共两行。

第一行输出$N$个整数， 表示每栋楼左边第一栋比自己高的楼的编号。

第二行输出$N$个整数， 表示每栋楼右边第一栋比自己高的楼的编号。

样例输入输出

5
3 1 2 5 4

-1 1 1 -1 4
4 3 4 -1 -1