Matryoshka Dolls

Denisson is an average enjoyer of Matryoshka dolls. A set of matryoshkas consists of a wooden figure that separates at the middle, top from bottom, to reveal a smaller figure of the same sort inside. That figure has another figure inside it, and so on. Recently he bought a set of these toys and placed them on the table in some order. The set has exactly $n$ dolls of different sizes, so the current order can be represented as a permutation $p$ of length $n$, where $p_i$ is the size of the $i$-th doll. Today Denisson wants to relax with his toys and plays the following game. First, he chooses a segment $[l, r]$ of the permutation. Then he takes the smallest matryoshka on this segment and places it into the matryoshka of the next size. The time for this step is $|i - j|$, where $p_i$ and $p_j$ are the sizes of the two smallest dolls on the chosen segment. He repeats this step until only one matryoshka is left on the segment. The total time of the game is the sum of the times of all steps. For each of the $q$ segments $[l_i, r_i]$, Denisson wants to know the total time of the game on that segment. He hopes you will not spend too much time finding these values.

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 10^5$, $1 \leq q \leq 5 \cdot 10^5$), the number of matryoshkas and the number of requests. The second line contains the permutation $p$ ($1 \leq p_i \leq n$). Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$), the endpoints of the $i$-th segment.

For the $i$-th request, print the total time needed to play the game on the segment $[l_i, r_i]$.