Shared code

// Author : -CHUNU-
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1000000007 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<long long,null_type,less
<long long>,rb_tree_tag, tree_order_statistics_node_update> o_set;
typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag, tree_order_statistics_node_update> o_multiset;
#define int long long

vector<vector<int>>sgt;
vector<vector<int>>sgtl;
vector<vector<int>>sgtr;
vector<int>v;
void build(int l, int r, int node){
    if(l == r){
        sgt[node].push_back(v[l]);
        return;
    }
    int mid = (l + r)/2;
    build(l, mid, 2 * node);
    build(mid + 1, r, 2 * node + 1);
    int i = 0, j = 0;
    int n = sgt[2 * node].size(), m = sgt[2 * node + 1].size();
    while(i < n && j < m){
        if(sgt[2 * node][i] < sgt[2 * node + 1][j]){
            sgt[node].push_back(sgt[2 * node][i]);
            sgtl[node].push_back(i);
            sgtr[node].push_back(j-1);
            i++;
        }else{
            sgt[node].push_back(sgt[2 * node + 1][j]);
            sgtl[node].push_back(i-1);
            sgtr[node].push_back(j);
            j++;
        }
    }

    while(i < n){
        sgt[node].push_back(sgt[2 * node][i]);
        sgtl[node].push_back(i);
        sgtr[node].push_back(j-1);
        i++;
    }

    while(j < m){
        sgt[node].push_back(sgt[2 * node + 1][j]);
        sgtl[node].push_back(i-1);
        sgtr[node].push_back(j);
        j++;
    }

    
}

int equery(int l, int r, int node, int idx, int tl, int tr){


   if(l > tr || r < tl)return 0;
   if(l >= tl && r <= tr){
    return idx + 1;
    
   }

    int mid = (l + r)/2;
    int sum = 0;

    if(tl <= mid && idx != -1){
        sum += equery(l, mid, 2 * node, sgtl[node][idx], tl, tr);
    }

    if(tr > mid && idx != -1){
        sum += equery(mid + 1, r, 2 * node + 1, sgtr[node][idx], tl, tr);
    }
    return sum;
}

// 1 1 2 3 3 4 5 5 

void solve(){
   int n, q;
   cin >> n >> q;
   v.resize(n + 1);
   for(int i = 1;i <= n;i++)cin >> v[i];
   sgt.resize(4 * n + 1);
   sgtl.resize(4 * n + 1);
   sgtr.resize(4 * n + 1);
   build(1, n, 1);
   sort(v.begin() + 1, v.end());
   v[0] = 0;


   while(q--){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int l = 0, r = n;
    int idx1 = 0;
    while(l <= r){
        int mid = (l + r)/2;
        if(v[mid] <= d){
            idx1 = mid;
            l = mid + 1;
        }else r = mid - 1;
    }
    int val1 = equery(1, n, 1, idx1-1, a, b);
    // cout << val1 <<" ";
   
    l = 0, r = n;
    idx1 = n;
    c--;
    while(l <= r){
        int mid = (l + r)/2;
        if(v[mid] <= c){
            idx1 = mid;
            l = mid + 1;
        }else r = mid - 1;
    }
    // cout << idx1 << endl;

    int val2 = equery(1, n, 1, idx1-1, a, b);
    // cout << val2 <<" ";

    cout << max(0ll, val1 - val2) << endl;
   }


}

int32_t main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int tc = 1;
    // cin >> tc;

    for(int i = 1;i <= tc;i++) {
        solve();
    }

    return 0;
}