Minimum Absolute Difference and Nearest Smaller Value Index

Given a sequence (A) of length (n) with all distinct elements, for each element (A_i) (with (1 \leq i \leq n)) you need to find: [ \min_{1 \leq j < i}|A_i - A_j| ] and the corresponding index (P_i) where the minimum is achieved. In case there are multiple indices (j) achieving the minimum, choose the one for which (A_j) is the smallest.

Note: For the first element (A_1) (i.e. when (i = 1)), there is no previous element, so you should output "0 0".

Input: The first line contains an integer (n) (the length of the sequence). The second line contains (n) space-separated integers (distinct), representing (A).

Output: Output (n) lines. The (i)-th line (1-indexed) should contain two integers: the minimum absolute difference (\left( \min_{1 \le j < i}|A_i - A_j| \right)) and the corresponding index (P_i). For (i = 1), print "0 0".

inputFormat

The first line contains a single integer \(n\), which is the number of elements in the sequence \(A\).
The second line contains \(n\) space-separated integers representing the sequence \(A\) (all elements are distinct).

outputFormat

Output \(n\) lines. For the \(i\)-th element \(A_i\), output two integers separated by a space: the minimum absolute difference from any previous element \(\left( \min_{1 \leq j < i}|A_i - A_j|\right)\) and the index \(P_i\) (1-indexed) that achieves this minimum. For \(i = 1\) where no previous element exists, output "0 0".

sample

5
1 5 3 19 18

0 0
4 1
2 1
14 2
1 4