L. Замечательные отрезки

Дан массив из $n$ целых чисел и $q$ запросов $(l, r)$. Для каждого запроса найдите наибольшее $k$, при котором отрезок $a_l, \ldots, a_r$ содержит все числа из промежутка $[x, x + k - 1]$ для какого-нибудь $x$.

В первой строке — число $n$ ($1 \le n \le 10^5$). Во второй — $n$ чисел $a_i$ ($1 \le a_i \le 10^5$). В третьей — число $q$ ($1 \le q \le 10^5$). В следующих $q$ строках — пары $l$, $r$ ($1 \le l \le r \le n$).

На каждый запрос выведите искомое $k$.