Tough Chief's Permutation Query

Legend tells of a mighty bald chief at the Minsk Aerospace Administration. Known for his boundless powers, his bald head, unusually hard scalp, and remarkable speed, he put a challenging task before a newcomer, the Pea Shooter.

You are given a permutation a₁, a₂, ..., a_n of length \(n\). There are \(m\) queries. For each query, you are given a segment \([l, r]\). Consider the subarray \(a_l, a_{l+1}, \dots, a_r\). Sort the elements of this subarray in increasing order (according to their values). Let the corresponding original indices of these sorted elements be \(i_1, i_2, \dots, i_k\) (note that these indices are from the original permutation). Your task is to compute the sum \[ S = \sum_{j=1}^{k-1} \left| i_{j+1} - i_j \right|. \] for each query.

Note: If the segment contains only one element, the sum is zero.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\), representing the length of the permutation and the number of queries.

The second line contains \(n\) distinct space-separated integers \(a_1, a_2, \dots, a_n\), which form a permutation of \(1, 2, \dots, n\).

Each of the following \(m\) lines contains two integers \(l\) and \(r\) \((1 \leq l \leq r \leq n)\) representing a query.

outputFormat

For each query, output a single integer — the sum of the absolute differences of the original indices of adjacent numbers in the sorted order of the segment.

sample

4 1
2 1 4 3
1 4

4