136. 邻值查找

给定一个长度为 $n$ 的序列 $A$,$A$ 中的数各不相同。

对于 $A$ 中的每一个数 $A_i$,求:

$\min_{1 \le j <i}|A_i-A_j|$

以及令上式取到最小值的 $j$(记为 $P_i$)。若最小值点不唯一,则选择使 $A_j$ 较小的那个。

输入格式

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

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

输出格式

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

分别表示当 $i$ 取 $2 \sim n$ 时,对应的 $\min_{1 \le j <i}|A_i-A_j|$ 和 $P_i$ 的值。

数据范围

$n \le 10^5$,$|A_i| \le 10^9$

输入样例:

3
1 5 3

输出样例:

4 1
2 1