#include <bits/stdc++.h>
int dr[] = {2, 2, -2, -2, 1, -1, 1, -1};
int dc[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dr1[] = {0, 0, 0, 1, 1, 1, -1, -1, -1};
int dc1[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int dr2[] = {-1, 0, 0, 1};
int dc2[] = {-1, -1, -2, -1};
using namespace std;
long long int rt[5000006], nw;
struct persistent {
  long long int l, r, s;
  persistent() { l = 0, r = 0, s = 0; }
};
persistent tree[5000006];
void update(long long int n, long long int b, long long int e, long long int pn,
            long long int val, long long int x) {
  if (b == e) {
    tree[n].s = tree[pn].s + val;
    return;
  }
  long long int mid = (b + e) >> 1;
  if (x <= mid) {
    if (tree[n].l == 0) tree[n].l = ++nw;
    tree[n].r = tree[pn].r;
    update(tree[n].l, b, mid, tree[pn].l, val, x);
  } else {
    if (tree[n].r == 0) tree[n].r = ++nw;
    tree[n].l = tree[pn].l;
    update(tree[n].r, mid + 1, e, tree[pn].r, val, x);
  }
  tree[n].s = tree[tree[n].l].s + tree[tree[n].r].s;
}
long long int query(long long int n, long long int pn, long long int b,
                    long long int e, long long int x, long long int y) {
  if (b > y || e < x) return 0;
  if (b >= x && e <= y) {
    return tree[n].s - tree[pn].s;
  }
  long long int mid = (b + e) >> 1;
  long long int p = query(tree[n].l, tree[pn].l, b, mid, x, y);
  long long int p1 = query(tree[n].r, tree[pn].r, mid + 1, e, x, y);
  return p + p1;
}
long long int sum(long long int x) { return (x * (x - 1)) / 2; }
long long int n;
long long int query(long long int x, long long int y, long long int x1,
                    long long int y1) {
  long long int k = query(rt[n], rt[x1], 1, n, 1, n);
  long long int k1 = query(rt[x - 1], rt[0], 1, n, 1, n);
  long long int k2 = query(rt[n], rt[0], 1, n, 1, y - 1);
  long long int k3 = query(rt[n], rt[0], 1, n, y1 + 1, n);
  long long int k4 = query(rt[n], rt[x1], 1, n, 1, y - 1);
  long long int k5 = query(rt[n], rt[x1], 1, n, y1 + 1, n);
  long long int k6 = query(rt[x - 1], rt[0], 1, n, 1, y - 1);
  long long int k7 = query(rt[x - 1], rt[0], 1, n, y1 + 1, n);
  return sum(k) + sum(k1) + sum(k2) + sum(k3) - sum(k4) - sum(k5) - sum(k6) -
         sum(k7);
}
long long int a[5000006];
int main() {
  long long int q, i, j, x;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  while (cin >> n >> q) {
    for (i = 1; i <= n; i++) {
      cin >> x;
      a[x] = i;
    }
    for (i = 1; i <= n; i++) {
      long long int x = a[i];
      rt[i] = ++nw;
      update(rt[i], 1, n, rt[i - 1], 1, x);
    }
    while (q--) {
      long long int l, r, d, u;
      cin >> l >> d >> r >> u;
      long long int ans = query(d, l, u, r);
      cout << sum(n) - ans << endl;
    }
  }
  return 0;
}
