题目描述

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

对于 $\red A$ 中的每一个数 $\red {A_i}$，求： $\red {min_{1≤j<i}|A_i−A_j|}$ 以及令上式取到最小值的 $\red j$（记为 $\red {P_i}$）。

若最小值点不唯一，则选择使 $\red {A_j}$较小的那个。

输入格式

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

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

输出格式

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

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

样例

输入样例

3
1 5 3

输出样例

4 1
2 1

提示

$\red {n≤10^5,|A_i|≤10^9}$