Code Submission Evaluation System Login

Datatähti 2019 loppu

Start:2019-01-17 12:00:00
End:2019-01-17 17:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2019 loppu - AuringonlaskuCSES - Auringonlasku

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ä)
Osatehtävä 2 (35 pistettä)
Osatehtävä 3 (49 pistettä)