The Closest Pair
题号：NC262593
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的正整数序列 a，保证每个数互不相同。

q 次询问一个区间 [l,r] 查询最小的 \max(a_i,a_j) \bmod \min(a_i,a_j) 满足 l\leq i<j\leq r。

输入描述:

第一行一个整数 n(2\leq n\leq 10^5)。

第二行 n 个非负整数，表示 a_i(1\leq a_i\leq 10^6)。

接下来一行一个整数 q(1\leq q\leq 3\times 10^5)。

接下来 q 行每行两个整数 l,r(1\leq l<r\leq n)。

输出描述:

接下来 q 行每行输出答案。
示例1

输入

复制 
4
4 7 5 3
3
1 2
1 3
2 4

输出

复制 
3
1
1