描述

给定一个长度为 n 的序列 A,A 中的数各不相同。对于 A 中的每一个数 A_i,求:
min(1≤j<i) ⁡|A_i-A_j|
以及令上式取到最小值的 j(记为 P_i)。若最小值点不唯一,则选择使 A_j 较小的那个

输入格式

第一行一个整数n,第二行n个数A_1~A_n。

输出格式

n-1行,每行2个用空格隔开的整数。分别表示当i取2~n时,对应的 min(1≤j<i) ⁡|A_i-A_j| 和 P_i 的值。

样例输入

3
1 5 3

样例输出

4 1
2 1

数据范围与约定

  • 对于30%的数据: n<=100
  • 对于70%的数据: n<=10^4
  • 对于100%的数据: n<=10^5, |A_i|<=10^9