CSES - Datatähti 2019 loppu - Auringonlasku
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Kaupungissa on rivissä nn 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 qq kyselyyn, joissa jokaisessa annetaan väli [a,b][a,b]. Jos oletetaan, että vain välin [a,b][a,b] pilvenpiirtäjät ovat olemassa, moniko niistä on auringossa?

Syöte

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

Syötteen toisella rivillä on nn kokonaislukua h1,h2,,hnh_1, h_2, \dots, h_n: pilvenpiirtäjien korkeudet.

Lopuksi syötteessä on qq riviä, joista kullakin on kaksi kokonaislukua aa ja bb (1abn1 \le a \le b \le n): kysely koskee väliä [a,b][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ä)

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

Osatehtävä 2 (35 pistettä)

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

Osatehtävä 3 (49 pistettä)

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