Problem description

W królestwie Bajtii wznosi się pasmo majestatycznych gór. Składa się ono z N szczytów, ponumerowanych od 1 do N z zachodu na wschód. Szczyt o numerze i ma wysokość H_i metrów.

Młody czarodziej Bajtazar testuje swój nowo utkany artefakt – Magiczny Dywan. Artefakt ten pozwala mu przemieszczać się w powietrzu, zużywając magiczną energię (manę). W każdej sekundzie lotu Bajtazar wykonuje dwie akcje jednocześnie:

1. Ruch w poziomie: Bajtazar wybiera jedną z trzech opcji:
   • Przemieszcza się na pozycję sąsiedniego wschodniego szczytu, zmieniając pozycję poziomą z i na i + 1.
   • Przemieszcza się na pozycję sąsiedniego zachodniego szczytu, zmieniając pozycję poziomą z i na i − 1.
   • Zatrzymuje się w miejscu (nie zmienia pozycji w poziomie).
2. Zmiana wysokości: Równolegle z ruchem poziomym, dywan zmienia swoją wysokość:
   • Wzniesienie się o jeden metr (kosztuje 4 jednostki many).
   • Opadnięcie o jeden metr (kosztuje 1 jednostkę many – dywan wspomaga się grawitacją).
   • Utrzymanie wysokości (kosztuje 2 jednostki many, by przeciwstawić się ciążeniu).

Oczywiście, Bajtazar musi unikać zderzenia ze skałami – w każdym momencie, gdy znajduje się nad szczytem i, jego wysokość musi wynosić co najmniej H_i.

Wielki Mag Bajtii zlecił Bajtazarowi dostarczenie Q ważnych zwojów. Podczas j-tej misji Bajtazar startuje dokładnie ze szczytu góry S_j i musi wylądować idealnie na szczycie góry T_j. Ponieważ regeneracja many trwa bardzo długo, Bajtazar chce zużyć jej jak najmniej. Pomóż mu obliczyć minimalną ilość many wymaganą dla każdej z misji!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę górskich szczytów.
W drugim wierszu znajduje się N liczb całkowitych H₁, H₂, …, H_N oddzielonych pojedynczymi odstępami, oznaczających wysokości kolejnych szczytów w metrach. W trzecim wierszu wejścia znajduje się jedna liczba całkowita Q, oznaczająca liczbę zapytań. W kolejnych Q wierszach znajdują się opisy poszczególnych misji. W j-tym z tych wierszy podane są dwie liczby całkowite S_j oraz T_j, oznaczające odpowiednio numer szczytu startowego i docelowego.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie Q wierszy. W j-tym wierszu powinna znaleźć się jedna liczba całkowita – minimalna liczba jednostek many niezbędna do wykonania lotu ze szczytu S_j na szczyt T_j.

Ograniczenia

2 ≤ N, Q ≤ 200 000, 1 ≤ H_i ≤ 10⁹, 1 ≤ S_j, T_j ≤ N

Ocenianie

Przykład

4
9 1 8 2
2
1 3
4 2

3
31

9
1 2 3 2 1 2 3 2 1
4
1 9
4 6
2 6
5 2

18
4
9
9

5
1 2 3 4 5
3
1 3
3 1
2 5

8
2
12