* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 1 000 000$

* Numerele sunt intervalul [$1,100 000$]

* Numerele sunt intervalul [{$1,100 000$}]

h2. Exemplu

h2. Indicatii de rezolvare
Problema se poate rezolva brut-force, cu complexitatea O(N*M), pentru fiecare interogare parcurgem tot intervalul si afisam minimul. Aceasta rezolvare obtine $30$ de puncte. O sursa care foloseste aceasta abordare gasiti "aici":job_detail/148408?action=view-source

O alta abordare poate o fi solutie care raspunde la un query in {$O(sqrt(n))$}. Vom folosi un vector {$A$} in care retinem minimul pe bucati de lungime {$sqrt(N)$}. In momentul unui query luam minimul dintr toate bucatile de lungime {$sqrt(N)$} incluse complet in intervalul dat, apoi pur si simplu parcurgem valorile din interval care nu le-am luat in considerare.

Putem de asemenea rezolva problema folosind un arbore de intervale ( vezi problema "Arbori de intervale":arbint ). Aceasta idee are complexitatea $O(NlogN+MlogN)$ si ar trebui sa obtina $60-70$ de puncte. O sursa care foloseste arbori de intervale gasiti "aici":job_detail/148285?action=view-source.
Pentru a obtine $100$ de puncte, vom folosi o idee mai simpla decat cea cu arbori de intervale si anume vom folosi algoritmul de Range minimum query care poate fi redus la complexitatea $O(NlogN + M)$.
O descriere mai pe larg a acestui algoritm gasiti "aici":preoni-2007/runda-2/solutii la problema $Plantatie$.