Rezolvare PBinfo #1899

Cerința

Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x, y ≤ n.

Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x, y]?”.

Date de intrare

Pe prima linie a fișierului afisminime.in sunt date numerele n și m. Pe a doua linie se vor afla n numere naturale, fiind elementele vectorului. Următoarele m linii vor conține câte 2 numere reprezentând valorile x și y, care definesc întrebările.

Date de ieșire

În fișierul de ieșire afisminime.out, vor fi m linii, fiecare conținând câte un număr, pe linia i aflându-se răspunsul pentru întrebarea i.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 1.000.000
• 1 ≤ x, y ≤ n

Exemplu:

afisminime.in

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

afisminime.out

1
3
2
2

Explicație

• în intervalul [1, 5] minimul este 1
• în intervalul [2, 3] minimul este 3
• în intervalul [3, 4] minimul este 2
• în intervalul [2, 4] minimul este 2