F. 纪念品
时间限制：每个测试点 $3$ 秒
内存限制：$512$ 兆字节

Artsem 正在度假，想给队友买纪念品。街道上有 $n$ 家纪念品商店，在第 $i$ 家商店里可以花 $a_i$ 美元买一件纪念品，并且不能在同一家商店买多于一件纪念品。他不希望队友之间产生嫉妒，因此他想买两件价格差尽可能小的纪念品。

Artsem 在这条购物街上逛了 $m$ 次。不知为何，在第 $i$ 天只有编号在 $[l_i, r_i]$ 之间的商店营业（很奇怪对吧？但你尝试过为区间查询问题编一个合情合理的背景故事吗？）。
对于每次购物，Artsem 想知道他在营业的商店中买两件不同纪念品的最小可能价格差。

换句话说，对于每次查询，你需要求出：

输入格式
第一行包含一个整数 $n$（$2 \le n \le 10^5$）。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）。

第三行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$）。

接下来 $m$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$，表示第 $i$ 天营业的商店区间（$1 \le l_i < r_i \le n$）。

输出格式
对于每个查询，输出一行一个整数——最小价格差。

样例输入

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

样例输出

0
1
1
3