#include <bits/stdc++.h>
using namespace std;

int read() {
    int a = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {
        a = a * 10 + c - 48;
        c = getchar();
    }
    return a;
}

const int _ = 1e5 + 2007, T = 318;
int N, M, P[_], RP[_];
long long ans[_ << 1];
struct query {
    int l, r, L, R, id, flag;
} now[_];

namespace inone {
vector<query> now;
void push(query cur) { now.push_back(cur); }

void brute() {
    sort(now.begin(), now.end(), [&](query p, query q) { return p.l < q.l; });
    static int pre = -1, sum[T + 1][T + 1], pos[T + 1];
    vector<int> pot;
    for (auto t : now) {
        if (t.l / T != pre) {
            pre = t.l / T;
            pot.clear();
            for (int i = pre * T; i < (pre + 1) * T; ++i) pot.push_back(P[i]);
            pot.push_back(-1);
            sort(pot.begin(), pot.end());
            memset(sum, 0, sizeof(sum));
            for (int i = pre * T, id = 1; i < (pre + 1) * T; ++i, ++id)
                for (int t = pos[id] = lower_bound(pot.begin(), pot.end(), P[i]) - pot.begin(), j = 1; j <= T;
                     ++j)
                    sum[id][j] = sum[id - 1][j] + sum[id][j - 1] - sum[id - 1][j - 1] + (j == t);
        }
        int qlow = lower_bound(pot.begin(), pot.end(), t.L) - pot.begin() - 1;
        for (int i = t.l; i <= t.r; ++i)
            if (P[i] >= t.L && P[i] <= t.R)
                ans[t.id] += (sum[i - pre * T][pos[i - pre * T + 1]] - sum[i - pre * T][qlow]) -
                             (sum[t.l - pre * T][pos[i - pre * T + 1]] - sum[t.l - pre * T][qlow]);
    }
}
}  // namespace inone

namespace scrat {
int sum[T][_], rk[_];

void prepare() {
    for (int i = 1; i <= N; ++i) ++sum[i / T][P[i]];
    for (int i = 0; i < T; ++i)
        for (int j = 1; j <= N; ++j) sum[i][j] += sum[i][j - 1];
    for (int i = 1; i < T; ++i)
        for (int j = 1; j <= N; ++j) sum[i][j] += sum[i - 1][j];

    for (int i = 0; i < T; ++i) {
        static int tmp[T];
        for (int j = 0; j < T; ++j) tmp[j] = i * T + j;
        sort(tmp, tmp + T, [&](int p, int q) { return P[p] < P[q]; });
        for (int j = 0; j < T; ++j) rk[tmp[j]] = j;
    }
}

void work(int l, int r, int L, int R, int id) {
    int bl = l / T, br = r / T;
    inone::push((query){ l, bl * T + T - 1, L, R, id });
    inone::push((query){ br * T, r, L, R, id });
    for (int i = l; i < bl * T + T; ++i)
        if (P[i] >= L && P[i] <= R)
            ans[id] += (sum[br - 1][R] - sum[br - 1][P[i]]) - (sum[bl][R] - sum[bl][P[i]]);
    for (int i = br * T; i <= r; ++i)
        if (P[i] >= L && P[i] <= R)
            ans[id] += (sum[br - 1][P[i]] - sum[br - 1][L - 1]) - (sum[bl][P[i]] - sum[bl][L - 1]);

    static int ptl[T + 1], ptr[T + 1];
    int pl = 0, pr = 0;
    ptl[T] = ptr[T] = -1;
    for (int i = l; i < bl * T + T; ++i)
        if (P[i] >= L && P[i] <= R)
            ptl[rk[i]] = i;
    for (int i = br * T; i <= r; ++i)
        if (P[i] >= L && P[i] <= R)
            ptr[rk[i]] = i;
    auto move = [&](int &pos, int *pot) {
        while (!pot[pos]) ++pos;
    };
    move(pl, ptl);
    move(pr, ptr);
    int cnt = 0;
    while (pl != T || pr != T)
        if (pl != T && (pr == T || P[ptl[pl]] < P[ptr[pr]])) {
            ++cnt;
            ptl[pl++] = 0;
            move(pl, ptl);
        } else {
            ans[id] += cnt;
            ptr[pr++] = 0;
            move(pr, ptr);
        }
}
}  // namespace scrat

namespace solve1 {
vector<query> now;
void push(query cur) { now.push_back(cur); }
int pot[T + 1][T + 1], cnt[T + 1];

void solve() {
    sort(now.begin(), now.end(), [&](query p, query q) { return p.R < q.R; });
    int pn = 0;
    for (int i = 1; i <= N; ++i) {
        int p = RP[i], id = p / T;
        for (int j = id; j; --j) pot[id][j] -= pot[id][j - 1];
        for (int j = 0; j < id; ++j) pot[id][j] += cnt[j];
        for (int j = id * T; j < p; ++j) pot[id][id] += P[j] < i;
        for (int j = 1; j <= id; ++j) pot[id][j] += pot[id][j - 1];
        ++cnt[id];
        while (pn < now.size() && now[pn].R == i) {
            for (int i = now[pn].l; i <= now[pn].r; ++i)
                ans[now[pn].id] += now[pn].flag * (pot[i][i] - (now[pn].l ? pot[i][now[pn].l - 1] : 0));
            ++pn;
        }
    }
}
}  // namespace solve1

namespace solve2 {
vector<query> now;
void push(query cur) { now.push_back(cur); }
long long cnt[_ << 1], tans[T + 1][T + 1];
int pre[_];

void solve() {
    for (int i = 0; i < T; ++i) {
        static int tmp[T];
        for (int j = 0; j < T; ++j) tmp[j] = i * T + j;
        sort(tmp, tmp + T, [&](int p, int q) { return P[p] < P[q]; });
        memset(pre, 0, sizeof(pre));
        for (int j = 0; j < T; ++j) ++pre[P[i * T + j]];
        for (int i = 1; i <= N; ++i) pre[i] += pre[i - 1];

        static int sum[T];
        memset(sum, 0, sizeof(sum));
        for (int j = 0; j < T; ++j) {
            for (int k = tmp[j] - i * T; k < T; ++k) ++sum[k];
            for (int k = j + 1; k < T; ++k) tans[j][k] = tans[j][k - 1] + sum[tmp[k] - i * T];
        }

        for (int j = 0; j < now.size(); ++j)
            if (now[j].l <= i && i <= now[j].r) {
                int pl = pre[now[j].L], pr = pre[now[j].R];
                ans[now[j].id] -= (pr - pl) * cnt[now[j].id];
                cnt[now[j].id] += pl;
                if (pl)
                    ans[now[j].id] -= tans[pl - 1][pr - 1];
            }
    }
}
}  // namespace solve2

int main() { 
    N = read();
    M = read();
    for (int i = 1; i <= N; ++i) RP[P[i] = read()] = i;
    scrat::prepare();

    for (int i = 1; i <= M; ++i) {
        int l = read(), r = read(), L = read(), R = read();
        if (l / T == r / T)
            inone::push((query){ l, r, L, R, i });
        else {
            scrat::work(l, r, L, R, i);
            l = l / T + 1;
            r = r / T - 1;
            if (l > r)
                continue;
            solve1::push((query){ l, r, 1, R, i, 1 });
            if (L != 1) {
                solve1::push((query){ l, r, 1, L - 1, i, -1 });
                solve2::push((query){ l, r, L - 1, R, i });
            }
        }
    }
    inone::brute();
    solve1::solve();
    solve2::solve();
    for (int i = 1; i <= M; ++i) printf("%lld\n", ans[i]);
    return 0;
}