Кролики

Разочаровавшись в олимпиадной информатике после школьного этапа, маленький мальчик Захар решил заняться разведением кроликов. Для этого он купил себе n кроликов и пронумеровал их
по неубыванию весов. Изначально i-й кролик весит wi килограмм.
Захар заметил, что если кроликов выстроить в шеренгу в порядке неубывания весов, то каждый
день у каждого кролика, такого что его вес меньше веса следующего, вес увеличивается на 1 килограмм. Более формально, каждый день вес i-го кролика увеличивается на 1 кг, если он не последний
в шеренге, и wi 6= wi+1. Все такие изменения происходят одновременно для всех кроликов. Такое
происходит до тех пор, пока веса всех кроликов не становятся равными весу последнего кролика в
шеренге.
Захар очень любознательный мальчик, а поэтому ему хочется ответить на m запросов: через
сколько дней вес кроликов больше не будет меняться, если в качестве шеренги взять кроликов с
номерами от li до ri
. Так как Захар разочарован в олимпиадной информатике, помочь ему предстоит
вам.
Формат входных данных
В первой строке задано единственное целое число n (1 6 n 6 200 000) — количество кроликов у
Захара.
В следующей строке заданы n целых чисел w1, w2, . . . , wn (1 6 wi 6 109
) — веса кроликов.
Гарантируется, что эти числа отсортированы по неубыванию, то есть wi 6 wi+1, для всех i 6 n − 1.
В следующей строке задано единственное целое число m (1 6 m 6 200 000) — количество запросов.
В следующих m строках задано по два целых числа li и ri (1 6 li 6 ri 6 n) — границы шеренги
из i-го запроса.
Формат выходных данных
На каждый запрос в отдельной строке выведите количество дней, после которых веса кроликов
не будет меняться. Можно показать, что такой день обязательно наступит.

0