Rezolvare PBinfo #3712

Cerința

Se dau un șir de N numere naturale nenule indexat de la 1 și Q query-uri de forma l r. Să se afișeze pentru fiecare query l r medianul secvenței l r din șir.

Date de intrare

Fișierul de intrare median_query.in conține pe prima linie numerele N și Q, iar pe a doua linie N numere naturale nenule separate prin spații. Pe următoarele Q linii se va afla câte o pereche de numere l r reprezentând query-urile.

Date de ieșire

Fișierul de ieșire median_query.out va conține răspunsurile la cele Q query-uri, câte unul pe fiecare linie.

Restricții și precizări

• 1 ≤ N, Q ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• 1 ≤ l ≤ r ≤ N
• medianul unei secvențe l r este valoarea care s-ar afla pe poziția [(r - l + 2) / 2] în secvența l r dacă aceasta ar fi sortată crescător, unde [x] = partea întreagă a numărului x.

Exemplu:

median_query.in

7 4
1 3 2 5 10 2 3
1 3
4 6
1 7
2 5

median_query.out

2
5
3
3

Explicație

Secvența 1 3 sortată crescător este: 1 2 3. Medianul acesteia este 2.

Secvența 4 6 sortată crescător este: 2 5 10. Medianul acesteia este 5.

Secvența 1 7 sortată crescător este: 1 2 2 3 3 5 10. Medianul acesteia este 3.

Secvența 2 5 sortată crescător este: 2 3 5 10. Medianul acesteia este 3.