2458. Задача торговца

Вдоль длинной дороги расположены несколько городов, пронумерованных от 1 до `n`. В каждом городе можно купить или продать некоторый товар. Этот товар имеет большой размер, поэтому торговец может везти с собой не более одной единицы товара. В `i`-м городе товар можно купить за `p_i` золотых, а продать за `(p_i\ -\ 1)` золотых.

Определите максимальную прибыль, которую может получить торговец при путешествии из города `s` в город `t`.

Первая строка ввода содержит одно целое число `n` (`2\ ≤\ n\ ≤\ 10^6`) – количество городов. Вторая строка ввода содержит `n` целых чисел `p_i` в диапазоне от 1 до `10^6` – цена товара в каждом городе. Третья строка ввода содержит одно целое число `m` (`1\ ≤\ m\ ≤\ 10^5`) – количество запросов на вычисление прибыли. Далее следует `n` строк, содержащих по два целых числа `s` и `t` (`1\ ≤\ s,\ t\ ≤\ n`, `s\ ≠\ t`) – номера начального и конечного города путешествия.

Для каждого запроса вывести на соответствующей строке одно целое число – максимальную прибыль, которую может получить торговец при путешествии из города `s` в город `t`.

7
1 2 7 5 3 10 9
3
1 7
4 7
7 1

11
6
3