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

对于 A 中的每一个数 $A_i$，求：

$min_{1≤j<i}|A_i−A_j|$

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

输入格式

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

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

输出格式

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

分别表示当 $i$ 取 2∼n 时，对应的$min_{1≤j<i}|A_i−A_j|$ 和 $P_i$的值。

数据范围

$n≤10^5,|A_i|≤10^9$

输入样例：

3
1 5 3

输出样例：

4 1
2 1