P10466 Nearest Value Query

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$.

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 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$.

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