Dreamoon создал документ с множеством сложных задач в notepad.exe. Документ состоит из n строк текста, ai обозначает длину i-ой строки. Теперь он хочет разобраться, как по этому документу можно побыстрее перемещать курсор, ведь документ очень длинный.
Предположим, что текущее положение курсора — (r, c), где r обозначает номер строки, а c — позицию внутри этой строки. В любой момент времени верно 1 ≤ r ≤ n и 0 ≤ c ≤ ar.
В notepad.exe мы можем использовать следующие шесть операций, чтобы передвигать курсор. Пусть текущее положение курсора — (r, c):
- клавиша вверх: новая позиция курсора будет (nr, nc) = (max(r - 1, 1), min(anr, c))
- клавиша вниз: новая позиция курсора будет (nr, nc) = (min(r + 1, n), min(anr, c))
- клавиша влево: новая позиция курсора будет (nr, nc) = (r, max(0, c - 1))
- клавиша вправо: новая позиция курсора будет (nr, nc) = (r, min(anr, c + 1))
- клавиша HOME: новая позиция курсора будет (nr, nc) = (r, 0)
- клавиша END: новая позиция курсора будет (nr, nc) = (r, ar)
Вам дано описание документа (n и последовательность ai) и q запросов от Dreamoon. Запрос имеет форму «какое минимальное количество нажатий клавиш необходимо для передвижения курсора от (r1, c1) до (r2, c2)?».
Выходные данные
Для каждого запроса выведите его результат в отдельной строке.
Примечание
В первом примере для первого запроса подходящей последовательностью нажатий является: HOME, вправо.
Для второго запроса подходящей последовательностью нажатий является: вниз, вниз, вниз, END, вниз.
Для третьего запроса подходящей последовательностью нажатий является: вниз, END, вниз.
Для четвёртого запроса подходящей последовательностью нажатий является: END, вниз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
2
10 5
1
1 0 1 5
|
3
|