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

• 1 \le n \le 2 \cdot 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le a_i \le 10^9
• 1 \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