Cerința

Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:

• x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

Să se răspundă la cele M întrebări.

Date de intrare

Fișierul de intrare easyxy.in conține pe prima linie numerele N și M. Pe următoarea linie se află N elemente ce reprezintă elementele vectorului. Pe următoarele M linii se află întrebările.

Date de ieșire

Fișierul de ieșire easyxy.out va conține pe fiecare linie i răspunsul la întrebarea i, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ N,M ≤ 100.000
• Elementele vectorului sunt ≤ 1.000.000.000
• Pentru orice întrebare, 1 ≤ x ≤ p ≤ y ≤ N

Exemplu:

easyxy.in

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

easyxy.out

2
5
5