Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y.

Cerința

Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare

Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire

Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare.

Restricții și precizări

• 1 ≤ n, T ≤ 200 000
• 0 ≤ a[i] ≤ 2 000 000 000
• 0 ≤ x ≤ y ≤ 2 000 000 000

Exemplu

Intrare

9 7
6 1 3 5 3 3 9 20 9
4 10
0 100
0 1
500 506
3 3
10 18
3 9

Ieșire

4
9
1
0
3
0
7

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 200001;
int a[MaxN], n, T;

int BsMax(int y); // ret poz celui mai mare numar din sirul a[] mai mic sau egal cu y
int BsMin(int x); // ret poz celui mai mic numar din sirul a[], mai mare sau egal cu x

int main()
{
    cin >> n >> T;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
        
    sort(a, a + n);
    int x, y, cnt;
    
    for (int i = 1; i <= T; ++i)
    {
        cin >> x >> y;
        int p2 = BsMax(y);
        int p1 = BsMin(x);
        if (p1 == -1)
            cout << 0 << '\n';
        else
            cout << p2 - p1 + 1 <<  '\n';
        
    }
    
}

int BsMin(int v)
{
    int l = 0, r = n - 1, m;
    int poz = -1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m] >= v)
        {
            poz = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    return poz;
}

int BsMax(int v)
{
    int l = 0, r = n - 1, m;
    int poz = -1;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (a[m] <= v)
        {
            poz = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    return poz;
}