Cerință

Definim costul unui șir altfel:

Pentru fiecare poziție $i$, $1 \leq i < N$, se va proceda astfel:

• Dacă $a_i<a_{i+1}$, atunci costul va crește cu $i$
• Dacă $a_i>a_{i+1}$, atunci costul va scădea cu $i$
• Dacă $a_i=a_{i+1}$, atunci costul devine $0$

Se dau $N$ numere, $a_1$, $a_2$, $a_3$, $\dots$, $a_N$ si $Q$ întrebări de forma:

Care este costul subsecvenței $[st, dr]$?

$\bold{Atenție!}$ Pozițiile subsecvenței $a_{st}$, $a_{st+1}$, $a_{st+2}$, $\dots$, $a_{dr-1}$, $a_{dr}$ nu au aceleași poziții în șirul inițial față de subsecvența $[st, dr]$. De exemplu:

Fie $N=7$, și șirul 1 3 3 4 2 1 9, subsecvența 3 4 2 1 au ca poziții 3, 4, 5 si 6 în șirul initial, dar în subsecvența $[2, 6]$ sunt pe pozițiile 2, 3, 4 și 5.

Date de intrare

Pe prima linie a fișierului de intrare sircost.in se găsește numarul natural, $N$. Pe a doua linie se vor afla $N$ numere naturale, reprezentând șirul $a_1$, $a_2$, $\dots$, $a_N$. Pe a treia linie se găseste numarul natural $Q$. Pe urmatoarele $Q$ linii se vor afla două numere naturale $st_i$, $dr_i$, reprezentând capetele celei de a $i$-a subsecvență.

Date de ieșire

Pe primele $Q$ a fișierului de ieșire sircost.out se vor afișa răspunsurile pentru cele $Q$ interogări.

Restricții și precizări

• $1 \leq N, Q \leq 2 \cdot 10^5$;
• $0 \leq a_i \leq 10^9$;

Exemplul 1

sircost.in

7
1 3 3 4 2 1 9
2
1 4
3 7

sircost.out

3
0

Explicație

Pentru subsecvența $[1, 4]$:

• $1<3$, costul devine $1$
• $3=3$, costul devine $0$
• $3<4$, costul devine $3$

Pentru subsecvența $[3, 7]$:

• $3<4$, costul devine $1$
• $4>2$, costul devine $-1$
• $2>1$, costul devine $-4$
• $1<9$, costul devine $0$