题目描述

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

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

以及令上式取到最小值的 $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$的值。

样例

3
1 5 3

4 1
2 1

数据范围

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

来源

• 算法竞赛进阶指南