Given an array of integers $a$ consisting of $n$ elements. For $q$ queries $l, r$, find $\text{min}(|a_i - a_j|)$ for $l \leq i < j \leq r$.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $a_i$.
- The third line contains an integer $q$.
- The next $q$ lines each contain two integers $l, r$ representing a query.
### Output
- For each query, print a single integer which is the result.
### Constraints
- $1 \leq n \leq 10^5$.
- $1 \leq q \leq 3 \times 10^5$.
- $1 \leq a_i \leq 10^9$.
### Example
Input:
```
8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7
```
Output:
```
0
1
1
3
```
