Auringonlasku

• Time limit: 1.00 s
• Memory limit: 512 MB

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$