P8078 [WC2022] Bald Chieftain

5s 512M -O2

It is said that in the Minsk Aerospace Bureau, there is a powerful Bald Chieftain. The Bald Chieftain has boundless magic power. He has no hair on his head, and his head is very hard. He can also run fairly fast. One day, the Peashooter came to the Minsk Aerospace Bureau. To test this newcomer, the Bald Chieftain gave him the following problem: Given a permutation $a_1, \dots, a_n$ of length $n$, there are $m$ queries. In each query, for the interval $[l, r]$, consider the numbers in this interval after sorting. Take the positions of these numbers in the original sequence, and compute the sum of the absolute differences between the positions of adjacent numbers in the sorted order.

The first line contains two integers $n, m$. The next line contains $n$ integers, representing the elements of the sequence $a$ in order. Then follow $m$ lines, each containing two integers $l, r$, representing one query.

For each query, output one integer per line, representing the answer.

**Sample Explanation** For the first query, $2, 3$ becomes $2, 3$ after sorting. Their positions in the original sequence are $3, 4$. The sum of absolute differences of positions of adjacent elements is $|3 - 4| = 1$. For the second query, $4, 2, 3, 1$ becomes $1, 2, 3, 4$ after sorting. Their positions in the original sequence are $5, 3, 4, 2$. The sum of absolute differences of positions of adjacent elements is $|5 - 3| + |3 - 4| + |4 - 2| = 5$. **Constraints** For $10\%$ of the testdata, $n, m \leq 10^3$. For another $10\%$ of the testdata, $n, m \leq 5 \times 10^4$. For another $10\%$ of the testdata, $n, m \leq 10^5$. For another $10\%$ of the testdata, $n, m \leq 2 \times 10^5$. For another $20\%$ of the testdata, $|a_i - i| \leq 10$. For another $20\%$ of the testdata, $m=\dfrac{n(n-1)}{2}$. For the remaining testdata, there are no special restrictions. For $100\%$ of the testdata, it holds that $1 \leq n, m \leq 5 \times 10^5$, $1 \leq a_i \leq n$, all $a_i$ are distinct, $1 \leq l \leq r \leq n$, and all values are integers. Translated by ChatGPT 5