题目描述

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

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

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

输入格式

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

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

输出格式

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

分别表示当 $i$ 取 $2 ～ n$ 时，对应的$\min\limits_{1 \le j < i} |A_i-A_j|$ 以及 $P_i$ 的值。

输入样例：

3
1 5 3

输出样例：

4 1
2 1

提示

当 $i=2$ 时，$A_2 = 5$，前面只有$A_1$， 所以最小值为 $5 - 1 = 4$， $j$ 为 $1$;

当 $i = 3$ 时，$A_3 = 3$，前面有$A_1 = 1， A_2 = 5$， 所以最小值为 $3 - 1 = 2$ 和 $5 - 3 = 2$， $j$ 取 $A_j$ 较小的为 $1$;

数据范围

• 50%的数据，$n \le 100$；
• 20%的数据，$n \le 10^4$；
• 5%的数据，$n = 10^5$，数列A为单调不降；
• 100%的数据，$n \le 10^5$,$|A_i| \le 10^9$。