Taulukossa on $n$ kokonaislukua, jotka on indeksoitu $1$:stä alkaen. Taulukkoa voi muuttaa tekemällä yhden tai useamman operaation, jossa valitaan yksi taulukon alkio ja kasvatetaan sitä yhdellä.

Tehtäväsi on vastata $q$ kyselyyn muotoa: kun tarkastellaan välin $[a,b]$ alitaulukkoa, mikä on pienin operaatioiden määrä, joiden jälkeen se on kasvava (eli jokainen alkio on yhtä suuri tai suurempi kuin edellinen alkio)?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: taulukon koko ja kyselyiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: taulukon sisältö.

Lopuksi on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: välin alku- ja loppukohta.

Tuloste

Tulosta jokaisesta kyselystä pienin muutosten määrä.

Esimerkki

Syöte:

5 3
2 10 4 2 5
3 5
2 2
1 4

Tuloste:

2
0
14

Selitys: Ensimmäisessä kyselyssä alitaulukko on $[4,2,5]$ ja riittää $2$ operaatiota, joiden avulla saadaan alitaulukko $[4,4,5]$. Toisessa kyselyssä alitaulukko on $[10]$. Kolmannessa kyselyssä alitaulukko on $[2,10,4,2]$.

Osatehtävä 1 (12 pistettä)

• $1 \le n,q \le 100$
• $1 \le x_i \le 100$
• $1 \le a \le b \le n$

Osatehtävä 2 (34 pistettä)

• $1 \le n,q \le 2\cdot10^5$
• $1 \le x_i \le 100$
• $1 \le a \le b \le n$

Osatehtävä 3 (54 pistettä)

• $1 \le n,q \le 2\cdot10^5$
• $1 \le x_i \le 10^9$
• $1 \le a \le b \le n$