Problem Description

Given a sequence $A$ of length $n$, all numbers in $A$ are distinct.

For each number $A_i$ in $A$, find:

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

and the index $j$ that makes the above expression reach its minimum (denoted as $P_i$). If the minimum is not unique, choose the one with the smaller $A_j$.

Input Format

The first line contains an integer $n$, the length of the sequence.

The second line contains $n$ integers $A_1 \sim A_n$, representing the values of the sequence, separated by spaces.

Output Format

Output a total of $n - 1$ lines, each line containing two integers separated by a space.

For each $i$ from $2 \sim n$, output the corresponding values of $\min_{1 \le j < i} |A_i - A_j|$ and $P_i$.

3
1 5 3

4 1
2 1

Hint

For $30\%$ of the testdata, $n \le 100$.

For $70\%$ of the testdata, $n \le 10^4$.

For $100\%$ of the testdata, $n \le 10^5, |A_i| \le 10^9$.

Translated by ChatGPT 5