题目描述

阿乐所在的年级举办了一场运动会。每个人在参加了 100 万个项目后分别获得了一个总分，所有人的总分互不相同。

阿乐认为，在学号小于自己的人中，总分与他最接近的同学就是他的最佳对手。现在按学号 $1 \sim n$ 的顺序输入所有同学的得分，请你找出第 $2 \sim n$ 号同学的最佳对手以及最佳对手的总分。

如果最佳对手不唯一（即有两个学号更小的同学，一人总分较高，一人总分较低，且他们的总分与当前同学总分的差值相等），选择总分更小的那个。

输入格式

第一行一个整数 $n$。

第二行按学号顺序输入 $n$ 个整数 $a_1 \sim a_n$，代表学号 $1 \sim n$ 号同学的总分。

输出格式

共 $n-1$ 行。第 $i$ 行输出两个整数，以空格隔开，分别表示第 $i+1$ 号同学的最佳对手的总分以及最佳对手的学号。

样例

3
1 5 3

4 1
2 1

数据范围与提示

• 对于 $50\%$ 的数据：$n \le 10^4$。
• 对于 $100\%$ 的数据：$n \le 10^5$，$|a_i| \le 10^9$。

来源

CSPJ-重点算法班