A. Arrayland's Challenge
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the digital realm of Arrayland, where data structures shape the foundations of society, the wise council has posed a challenging task to sharpen the minds of its citizens. The challenge involves understanding the subtle differences within the ordered structures, specifically within subarrays.

You are given an array of integers $$$A$$$ of size $$$N$$$. Accompanying the array, you receive $$$Q$$$ queries. Each query specifies a subarray defined by two indices $$$L$$$ and $$$R$$$ (where $$$1 \leq L \lt R \leq N$$$), and you are tasked with finding the smallest absolute difference between any two distinct elements within this subarray.

For each query, determine the minimum absolute difference between any two distinct elements contained in the subarray from index $$$L$$$ to $$$R$$$.

Input

The first line of input contains an integer $$$N$$$ $$$(2 \leq N \leq 10^4)$$$, the size of the array. The second line contains $$$N$$$ integers $$$a_i$$$ separated by spaces $$$(1 \leq a_i \leq 10^6)$$$, the elements in the array.

The third line contains an integer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$, the number of queries to answer.

Each of the next $$$Q$$$ lines contains two integers $$$L$$$, and $$$R$$$ $$$(1 \leq L \lt R \leq N)$$$ representing the indices of the subarray for the query.

Output

Print $$$Q$$$ lines, where the $$$i$$$-th line contains a sintle integer representing the answers for to the $$$i$$$-th query.

Examples
Input
10
4 5 1 3 2 1 4 6 7 8
3
1 10
3 6
7 10
Output
0
0
1
Input
8
3 45 1 2 3 4 4 4
2
1 8
1 2
Output
0
42