#37. 邻值查找

邻值查找

给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 AiA_i,求:

image

以及令上式取到最小值的 j(记为 PiP_i)。若最小值点不唯一,则选择使 AjA_j 较小的那个。

输入格式

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

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

输出格式

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

分别表示当i取2~n时,对应的image的值。

数据范围

n105n \le 10^5,A_i109|A\_i| \le 10^9

输入样例:

3
1 5 3

输出样例:

4 1
2 1