Equalizing Pillars

There are $N$ pillars made of bricks. The height of each pillar is the number of bricks in that pillar.

In this problem, you have to answer $Q$ independent queries on these pillars. For each query, you will be given a range $L$ and $R$. You have to find out the minimum number of moves to make all the pillars equal in height within the range of $L$ and $R$.

In one move, you can add or remove a single brick from a pillar within the range.

Input

The first line of the input will contain two space-separated integers $N$ and $Q (1 \leq N, Q \leq 10^5)$, the number of pillars and the number of queries, respectively.

The next line will contain $N$ space-separated integers, $i^{\text{th}}$ integer denoting the height of $i^{\text{th}}$ pillar. The heights will be in range $[1, 10^9]$.

The next $Q$ lines will describe the queries. For each query, you will be given two space-separated integers $L$ and $R (1 \leq L \leq R \leq N)$, the range to be considered for the query.

Output

For each query, print the answer in a line in the same order in which the queries appear in the input.

Sample

Input	Output
5 3 1 6 2 3 5 2 4 1 5 4 4	4 8 0
Explanation of the first query: We have numbers 6, 2, and 3. If we want to make all of them equal to 4, we have to decrease value 6 twice, increase value 2 twice, and the value 3 once. Hence, we need 5 moves. If we want to make all of them equal to 3, we have to decrease value 6 thrice, and increase value 2 once. Here, we need a total of 4 moves. So the optimal answer will be 4 moves.