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$
