邻值查找

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 $A\_i$，求：

$\min_{1 \le j

以及令上式取到最小值的 j（记为 $P\_i$）。若最小值点不唯一，则选择使 $A\_j$ 较小的那个。

输入格式

第一行输入整数n，代表序列长度。

第二行输入n个整数$A\_1…A\_n$,代表序列的具体数值，数值之间用空格隔开。

输出格式

输出共n-1行，每行输出两个整数，数值之间用空格隔开。

分别表示当i取2~n时，对应的$\min_{1 \le j

数据范围

$n \le 10^5$,$|A\_i| \le 10^9$

输入样例：

3
1 5 3

输出样例：

4 1
2 1

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解