RoAlgo PreOJI 2024 IX | sircost

Task

We define the cost of a sequence differently:

For each position $i$, $1 \leq i < N$, proceed as follows:

• If $a_i < a_{i+1}$, then the cost will increase by $i$
• If $a_i > a_{i+1}$, then the cost will decrease by $i$
• If $a_i = a_{i+1}$, then the cost becomes $0$

Given $N$ numbers, $a_1$, $a_2$, $a_3$, $\dots$, $a_N$, and $Q$ questions of the form:

What is the cost of the subarray $[st, dr]$?

$\bold{Attention!}$ The positions of the subarray $a_{st}$, $a_{st+1}$, $a_{st+2}$, $\dots$, $a_{dr-1}$, $a_{dr}$ do not have the same positions in the initial sequence compared to the subarray $[st, dr]$. For example:

Let $N=7$, and the sequence 1 3 3 4 2 1 9, the subarray 3 4 2 1 has positions 3, 4, 5, and 6 in the initial sequence, but in the subarray $[2, 6]$ they are in positions 2, 3, 4, and 5.

Input data

The first line of the input file sircost.in contains the natural number $N$. The second line contains $N$ natural numbers representing the sequence $a_1$, $a_2$, $\dots$, $a_N$. The third line contains the natural number $Q$. The next $Q$ lines contain two natural numbers $st_i$, $dr_i$, representing the endpoints of the $i$-th subarray.

Output data

The first $Q$ lines of the output file sircost.out will contain the answers for the $Q$ queries.

Constraints and clarifications

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

Example 1

sircost.in

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

sircost.out

3
0

Explanation

For the subarray $[1, 4]$:

• $1<3$, the cost becomes $1$
• $3=3$, the cost becomes $0$
• $3<4$, the cost becomes $3$

For the subarray $[3, 7]$:

• $3<4$, the cost becomes $1$
• $4>2$, the cost becomes $-1$
• $2>1$, the cost becomes $-4$
• $1<9$, the cost becomes $0$