Kaupungissa on rivissä n pilvenpiirtäjää. Laskeva aurinko valaisee pilvenpiirtäjiä vasemmalta, ja pilvenpiirtäjä on auringossa, jos se on korkeampi kuin mikään sen vasemmalla puolella oleva pilvenpiirtäjä.

Tehtäväsi on vastata q kyselyyn, joissa jokaisessa annetaan väli [a,b]. Jos oletetaan, että vain välin [a,b] pilvenpiirtäjät ovat olemassa, moniko niistä on auringossa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: pilvenpiirtäjien määrä ja kyselyjen määrä. Pilvenpiirtäjät on numeroitu 1,2,\dots,n.

Syötteen toisella rivillä on n kokonaislukua h_1, h_2, \dots, h_n: pilvenpiirtäjien korkeudet.

Lopuksi syötteessä on q riviä, joista kullakin on kaksi kokonaislukua a ja b (1 \le a \le b \le n): kysely koskee väliä [a,b].

Tuloste

Tulosta kutakin kyselyä kohden yksi kokonaisluku omalle rivilleen: auringossa olevien pilvenpiirtäjien määrä.

Esimerkki

Syöte:

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

Tuloste:

1
3
1

Osatehtävä 1 (16 pistettä)

• 1 \leq n, q \leq 2000
• 1 \leq h_{i} \leq 10^9

Osatehtävä 2 (35 pistettä)

• 1 \leq n \leq 10^5
• 1 \leq q \leq 2 \cdot 10^5
• 1 \leq h_{i} \leq 100

Osatehtävä 3 (49 pistettä)

• 1 \leq n \leq 10^5
• 1 \leq q \leq 2 \cdot 10^5
• 1 \leq h_{i} \leq 10^9