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.

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.

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

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 |

Login to submit.

48%
Solution Ratio

solaimanopeEarliest,

tanu_RUETFastest, 0.1s

Nasif_44thLightest, 12 MB

mh755628Shortest, 1622B

Toph uses cookies. By continuing you agree to our Cookie Policy.