题目描述

给定一个可能含有重复值的数组 $arr$，找到每一个 i 位置左边和右边离 i 位置最近且值比 $arr_i$ 小的位置。返回所有位置相应的信息。

输入描述：

第一行输入一个数字 n，表示数组 $arr$ 的长度。
以下一行输入 n 个数字，表示数组的值

输出描述：

输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例1

输入：

7
3 4 1 5 6 2 7

输出：

-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

备注：

• $1 \le n \le 10^6$
• $-10^6 \le arr_i \le 10^6$