Tiltai

Architektas Marijonas bando optimizuoti susisiekimą kalnuotoje vietovėje, kurioje kalnai išsidėstę tiesėje.

Jis aprašė vietovę kaip $N$ dydžio masyvą $A$, kurio $k$-toji pozicija nusako $k$-tojo kalno aukštį.

Dabar jis planuoja pastatyti tiltą tarp dviejų kalnų. Marijonas dar nežino, tarp kurių kalnų jis statys tiltą, bet jam įdomu sužinoti statybų kainą, jei tiltas būtų statomas tarp kalnų $L_i$ ir $R_i$.

Statybų kaina tarp tiltų apskaičiuojama taip:

• tilto aukščiu Marijonas pasirenka šoninių kalnų aukščių vidurkio sveikąją dalį $M_i = \left\lfloor \frac{A[L_i] + A[R_i]}{2}\right\rfloor$;
• toliau tiltas tiesiamas virš kiekvieno kalno, kurio indeksas $k_i$ yra $L_i ≤ k_i ≤ R_i$;
• jei kalno aukštis $A[k_i ] ≤ M_i$, Marijonui reikės pastatyti pastolius. Pastolių statymo kaina yra $M_i − A[k_i ]$;
• jei kalno aukštis $A[k_i ] > M_i$, Marijonui reikės iškasti tunelį. Tunelio kaina yra $1$.

Marijonas gali lengvai apskaičiuoti vieno tilto kainą, tačiau jam įdomu rasti kainą tarp $Q$ kalnų porų. Ar galite padėti Marijonui rasti $Q$ tiltų statymo kainas?

Pirmoje eilutėje pateiktas kalnų masyvo dydis $N$.

Antroje eilutėje pateikti tarpu atskirti sveikieji skaičiai $A[1], A[2], \dots , A[N]$.

Trečioje eilutėje pateiktas užklausų skaičius $Q$.

Likusiose $Q$ eilučių pateikta po du tarpu atskirtus sveikuosius skaičius $L_i$, $R_i$.

Išveskite $Q$ eilučių, kiekvienoje iš jų pateikdami vieną skaičių: tilto statomo tarp kalnų $L_i$ ir $R_i$ kainą (į užklausas atsakoma eilės tvarka).

• $1 ≤ N, Q ≤ 100\, 000$
• $1 ≤ L_i ≤ R_i ≤ N$ ($1 ≤ i ≤ Q$)
• $1 ≤ A[i] ≤ 10\, 000$ ($1 ≤ i ≤ N$)