题目描述

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

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

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

输入格式

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

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

输出格式

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

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

样例

输入样例：

3
1 5 3

输出样例：

4 1
2 1

样例解释

序列：$A_1=1, A_2=5, A_3=3$

对于 $i=2$：

• $j=1$：$|5-1|=4$ 最小值是 4，$P_2=1$，输出 4 1

对于 $i=3$：

• $j=1$：$|3-1|=2$
• $j=2$：$|3-5|=2$ 最小值都是 2，选择使 $A_j$ 较小的 $j=1$（$A_1=1 < A_2=5$），所以 $P_3=1$，输出 2 1

数据范围

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

时空限制

• 时间限制：1 秒
• 空间限制：64 MB