题目描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数Ai​，求：min(1≤j<i)⁡∣Ai​−Aj​∣
以及令上式取到最小值的 j（记为 Pi​）。若最小值点不唯一，则选择使 Aj​较小的那个。

输入格式

第一行一个整数n，第二行n个数A1​ An​。

输出格式

n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的 min(1≤j<i)⁡∣Ai​−Aj​∣和Pi​ 的值。

样例

3
1 5 3

4 1
2 1

提示

对于30%的数据:n≤100
对于70%的数据: n≤104
对于100%的数据: n≤105,∣Ai​∣≤109