CSES - Kolikot
  • Time limit: 4.00 s
  • Memory limit: 256 MB

Uolevilla on nn kolikon kokoelma. Kolikot ovat rivissä niin, että kohdassa ii olevan kolikon arvo on aia_i.

Uolevilla on kiire lähteä matkalle, joten hän aikoo ottaa yhtenäisen välin vierekkäisiä kolikkoja mukaansa.

Tehdäkseen välin valinnan hyvin Uolevi haluaa tehdä kyselyitä. Jokaisessa kyselyssä pitää selvittää pienin hinta, jota ei voi maksaa tasarahalla, jos otetaan kolikot väliltä [li,ri][l_i, r_i].

Syöte

Syötteen ensimmäisellä rivillä on luvut nn ja mm – kolikoiden määrä ja kyselyjen määrä. Seuraavalla rivillä on nn lukua, a1,ana_1, \ldots a_n – kolikoiden arvot. Sen jälkeen on mm riviä joilla on 22 lukua lil_i ja rir_i – kyselyn välin alku ja loppu.

Tuloste

Tulosta jokaiselle kyselylle pienin hinta, jota ei voi maksaa tasarahalla välin kolikoilla.

Rajat

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1ai1091 \le a_i \le 10^9
  • 1lirin1 \le l_i \le r_i \le n

Esimerkki

Syöte:

5 5
2 1 5 3 1
1 5
1 3
1 1
2 4
2 5

Tuloste:

13
4
1
2
11