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