Code Submission Evaluation System Login

IOI-leiri 2016

Kolikot


Task | Statistics


CSES - KolikotCSES - Kolikot

Time limit:4.00 s Memory limit:256 MB

Uolevilla on $n$ kolikon kokoelma. Kolikot ovat rivissä niin, että kohdassa $i$ olevan kolikon arvo on $a_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ä $[l_i, r_i]$.

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $m$ – kolikoiden määrä ja kyselyjen määrä. Seuraavalla rivillä on $n$ lukua, $a_1, \ldots a_n$ – kolikoiden arvot. Sen jälkeen on $m$ riviä joilla on $2$ lukua $l_i$ ja $r_i$ – kyselyn välin alku ja loppu.

Tuloste

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

Rajat
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