该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

哈尔滨商业大学有 $n$ 个签到窗口，每个窗口有唯一的速度值 $A_i$（保证各不相同）。

第 $i$ 个新生$（i ≥ 2）$到达时，系统会从之前 $1$ 到 $i-1$ 号窗口中选择速度差值最小的窗口作为参考。

请为每个新生输出：

最小速度差值 $min|A_i - A_j|（1 ≤ j < i）$

对应的窗口编号 $j$

如果最小值点不唯一（即多个 $j$ 使差值相同），则选择使 $A_j$ 较小的那个。

输入格式

第一行输入一个整数 $n（1 ≤ n ≤ 10^5）$，表示窗口总数

第二行输入 $n$ 个整数 $A_1...A_n（|A_i| ≤ 10^9）$，表示每个窗口的速度值，用空格隔开

输出格式

输出共 $n-1$ 行，每行两个整数，用空格隔开。

第 $i-1$ 行（$i$ 从 $2$ 到 $n$）表示：当前新生 $i$ 的最小速度差值 和 对应的窗口编号。

样例

5
1 8 3 5 2

7 1
2 1
2 3
1 1

样例解释

依次处理每个新生（从第 2 个开始）：

i = 2，A[2] = 8

之前窗口只有 [1]

计算差值：|8-1| = 7

最小差值为 7，对应窗口 j = 1

输出：7 1

i = 3，A[3] = 3

之前窗口有 [1, 8]

计算差值：|3-1| = 2，|3-8| = 5

最小差值为 2，对应窗口 j = 1

输出：2 1

i = 4，A[4] = 5

之前窗口有 [1, 8, 3]

计算差值：|5-1| = 4，|5-8| = 3，|5-3| = 2

最小差值为 2，对应窗口 j = 3

输出：2 3

i = 5，A[5] = 2

之前窗口有 [1, 8, 3, 5]

计算差值：|2-1| = 1，|2-8| = 6，|2-3| = 1，|2-5| = 3

最小差值为 1，但有两个窗口都达到这个差值：j = 1（A[1]=1）和 j = 3（A[3]=3）

根据规则，选择 A[j] 较小的那个，A[1]=1 < A[3]=3，所以选择 j = 1

输出：1 1