题目描述

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

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

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

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

输入格式

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

第二行输入 $n$ 个整数 $A_1 \sim 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

说明/提示

输入样例 #2

16
787438195 166331658 -608443638 -603939888 818711908 187646748 -971899318 376887346 429541777 655442089 -897777401 734073977 -300286317 -288966802 -887254786 308288314

输出样例 #2

621106537 1
774775296 2
4503750 3
31273713 1
21315090 2
363455680 3
189240598 6
52654431 8
131996106 1
74121917 7
53364218 1
303653571 4
11319515 13
10522615 11
68599032 8

输入样例 #3

20
700241720 963756590 192073589 828453187 647948143 -300584399 26065646 -355767093 -408659442 566219914 415537910 -147502368 -214088091 -810322387 -138018203 770127342 589658487 361200528 -184171764 -483868729

输出样例 #3

263514870 1
508168131 1
128211467 1
52293577 1
492657988 3
166007943 3
55182694 6
52892349 8
81728229 5
150682004 10
153082031 6
66585723 12
401662945 9
9484165 12
58325845 4
23438573 10
54337382 11
29916327 13
75209287 9

数据范围

对于 $30\%$ 的数据 $n \le 100$。

对于 $70\%$ 的数据 $n \le 10^4$。

对于 $100\%$ 的数据 $n \le 10^5,|A_i| \le 10^9$。