Dế Mèn có mảng ~a~ gồm ~n~ số nguyên. Anh ấy cần trả lời ~q~ truy vấn sau:

• ~l\ r~: Tìm cặp ~(i, j)~ ~(l \le i < j \le r)~ sao cho ~|a_i - a_j|~ nhỏ nhất có thể, in ra giá trị đó.

Tất nhiên Dế Mèn biết bài này giải bằng chia căn cơ bản, nhưng Dế Mèn đang lười nên các bạn code giúp nhé!

Input

• Dòng đầu gồm số nguyên dương ~n~ là độ dài mảng ~a~ ~(2 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
• Dòng thứ ba gồm số nguyên dương ~q~ là số truy vấn cần trả lời (~1 \le q \le 3 \cdot 10^5~).
• ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~l, r~ tương ứng với một truy vấn ~(1 \le l < r \le n)~.

Output

In ra ~q~ dòng tương ứng câu trả lời cho ~q~ truy vấn.

Sample Input 1

8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7

Sample Output 1

0
1
1
3