- Time limit: 1.00 s
- Memory limit: 512 MB
Kaupungissa on rivissä 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 kyselyyn, joissa jokaisessa annetaan väli . Jos oletetaan, että vain välin pilvenpiirtäjät ovat olemassa, moniko niistä on auringossa?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : pilvenpiirtäjien määrä ja kyselyjen määrä. Pilvenpiirtäjät on numeroitu .
Syötteen toisella rivillä on kokonaislukua : pilvenpiirtäjien korkeudet.
Lopuksi syötteessä on riviä, joista kullakin on kaksi kokonaislukua ja (): kysely koskee väliä .
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