Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

E. Dreamoon и блокнот
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Dreamoon создал документ с множеством сложных задач в notepad.exe. Документ состоит из n строк текста, ai обозначает длину i-ой строки. Теперь он хочет разобраться, как по этому документу можно побыстрее перемещать курсор, ведь документ очень длинный.

Предположим, что текущее положение курсора — (r, c), где r обозначает номер строки, а c — позицию внутри этой строки. В любой момент времени верно 1 ≤ r ≤ n и 0 ≤ c ≤ ar.

В notepad.exe мы можем использовать следующие шесть операций, чтобы передвигать курсор. Пусть текущее положение курсора — (r, c):

  1. клавиша вверх: новая позиция курсора будет (nr, nc) = (max(r - 1, 1), min(anr, c))
  2. клавиша вниз: новая позиция курсора будет (nr, nc) = (min(r + 1, n), min(anr, c))
  3. клавиша влево: новая позиция курсора будет (nr, nc) = (r, max(0, c - 1))
  4. клавиша вправо: новая позиция курсора будет (nr, nc) = (r, min(anr, c + 1))
  5. клавиша HOME: новая позиция курсора будет (nr, nc) = (r, 0)
  6. клавиша END: новая позиция курсора будет (nr, nc) = (r, ar)

Вам дано описание документа (n и последовательность ai) и q запросов от Dreamoon. Запрос имеет форму «какое минимальное количество нажатий клавиш необходимо для передвижения курсора от (r1, c1) до (r2, c2)?».

Входные данные

В первой строке записано целое число n(1 ≤ n ≤ 400, 000) — количество строк текста.

Во второй строке записано n целых чисел a1, a2, ..., an(1 ≤ ai ≤ 108).

В третьей строке записано целое число q(1 ≤ q ≤ 400, 000).

В каждой из следующих q строк записано по четыре целых числа r1, c1, r2, c2, образующих запрос (1 ≤ r1, r2 ≤ n, 0 ≤ c1 ≤ ar1, 0 ≤ c2 ≤ ar2).

Выходные данные

Для каждого запроса выведите его результат в отдельной строке.

Примеры
Входные данные
9
1 3 5 3 1 3 5 3 1
4
3 5 3 1
3 3 7 3
1 0 3 3
6 0 7 3
Выходные данные
2
5
3
2
Входные данные
2
10 5
1
1 0 1 5
Выходные данные
3
Примечание

В первом примере для первого запроса подходящей последовательностью нажатий является: HOME, вправо.

Для второго запроса подходящей последовательностью нажатий является: вниз, вниз, вниз, END, вниз.

Для третьего запроса подходящей последовательностью нажатий является: вниз, END, вниз.

Для четвёртого запроса подходящей последовательностью нажатий является: END, вниз.