Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Equalizing Pillars

By Peregrine_Falcon · Limits 1s, 1.0 GB

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

InputOutput
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.


    Discussion

    Statistics


    48% Solution Ratio

    solaimanopeEarliest, 1M ago

    tanu_RUETFastest, 0.1s

    Nasif_44thLightest, 12 MB

    mh755628Shortest, 1622B

    Submit

    Login to submit

    Editorial

    It is easy to prove that for a given range $[L,R]$ the best answer comes when we make the pillers he...

    Related Contests