Adjacent Differences in Original Positions After Sorting

Given a permutation \(a_1, a_2, \ldots, a_n\) of \(n\) distinct integers, you are asked to answer \(m\) queries. For each query with the interval \([l, r]\), consider the subarray \(a_l, a_{l+1}, \ldots, a_r\). Sort these numbers by their value to form a new sequence \(b_1, b_2, \ldots, b_k\). Let \(p_i\) be the original position (i.e. index in the given permutation) of \(b_i\). Your task is to compute the sum

[ \sum_{i=1}^{k-1} |p_{i+1} - p_i| ]

This sum is the total absolute difference between the original positions of adjacent numbers in the sorted order.

inputFormat

The first line contains two integers \(n\) and \(m\), denoting the length of the permutation and the number of queries respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), representing the permutation.

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

outputFormat

For each query, output a single integer - the sum of absolute differences of the original positions of adjacent numbers after sorting the corresponding subarray by value.

sample

3 3
3 1 2
1 3
1 1
2 3

3
0
1