#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


#ifdef LOCAL_
constexpr int MAX_N = 100;
constexpr int B = 3;
constexpr int MAX_A = MAX_N / B;
#else
constexpr int MAX_N = 100'000;
constexpr int B = 400;
constexpr int MAX_A = MAX_N / B;
#endif

int N, A;
vector<int> P, invP;

#define P do_not_use_P
#define invP do_not_use_invP
struct Solver {
  vector<int> ps;
  int cntLess[MAX_A + 1][MAX_N + 1];
  int inside[MAX_A + 1][B + 1][B + 1];
  int section[MAX_A + 1][MAX_N + 1];
  void build(const vector<int> &ps_) {
    ps = ps_;
    for (int a = 0; a <= A; ++a) {
      const int len = min(B, N - a * B);
      fill(cntLess[a], cntLess[a] + (N + 1), 0);
      for (int b = 0; b < len; ++b) {
        ++cntLess[a][ps[a * B + b] + 1];
      }
      for (int y = 0; y < N; ++y) {
        cntLess[a][y + 1] += cntLess[a][y];
      }
      for (int b = 0; b < len; ++b) {
        copy(inside[a][b], inside[a][b] + (B + 1), inside[a][b + 1]);
        for (int e = cntLess[a][ps[a * B + b]] + 1; e <= B; ++e) {
          ++inside[a][b + 1][e];
        }
      }
    }
    for (int a = 0; a < A; ++a) {
      for (int y = 0; y <= N; ++y) {
        section[a + 1][y] = section[a][y] + cntLess[a][y];
      }
    }
  }
  Int calcInside(int a, int b0, int b1, int y0, int y1) const {
    assert(0 <= a); assert(a <= A);
    assert(0 <= b0); assert(b0 <= b1); assert(b1 <= min(B, N - a * B));
    Int ret = 0;
    for (int b = b0; b < b1; ++b) {
      const int y = ps[a * B + b];
      if (y0 <= y && y < y1) {
        // [a B + b0, a B + b) * [y0, y)
        const int e0 = cntLess[a][y0];
        const int e = cntLess[a][y];
        ret += (inside[a][b][e] - inside[a][b][e0] - inside[a][b0][e] + inside[a][b0][e0]);
      }
    }
    return ret;
  }
  Int calc(int x0, int x1, int y0, int y1) const {
    assert(0 <= x0); assert(x0 <= x1); assert(x1 <= N);
    const int a0 = x0 / B + 1;
    const int a1 = x1 / B;
    Int ret = 0;
    if (a0 <= a1) {
      // left, left
      ret += calcInside(a0 - 1, x0 - (a0 - 1) * B, B, y0, y1);
      // left, block
      for (int x = x0; x < a0 * B; ++x) if (y0 <= ps[x] && ps[x] < y1) {
        // [a0 B, a1 B) * (ps[x], y1)
        ret += (section[a1][y1] - section[a1][ps[x] + 1] - section[a0][y1] + section[a0][ps[x] + 1]);
      }
      // left, right
      for (int x = a1 * B; x < x1; ++x) if (y0 <= ps[x] && ps[x] < y1) {
        // [x0, a0 B) * [y0, ps[x])
        const int b0 = x0 - (a0 - 1) * B;
        const int e0 = cntLess[a0 - 1][y0];
        const int e = cntLess[a0 - 1][ps[x]];
        ret += (inside[a0 - 1][B][e] - inside[a0 - 1][B][e0] - inside[a0 - 1][b0][e] + inside[a0 - 1][b0][e0]);
      }
      // block, block: ignore
      // block, right
      for (int x = a1 * B; x < x1; ++x) if (y0 <= ps[x] && ps[x] < y1) {
        // [a0 B, a1 B) * [y0, ps[x])
        ret += (section[a1][ps[x]] - section[a1][y0] - section[a0][ps[x]] + section[a0][y0]);
      }
      // right, right
      ret += calcInside(a1, 0, x1 - a1 * B, y0, y1);
    } else {
      ret += calcInside(a1, x0 - a1 * B, x1 - a1 * B, y0, y1);
    }
    return ret;
  }
};
Solver solverP, solverInvP;
#undef P
#undef invP

Int f[MAX_A + 1][MAX_A + 1][MAX_A + 1];
int g[MAX_A + 1][MAX_A + 1][MAX_A + 1];

void build() {
  invP.assign(N, -1);
  for (int x = 0; x < N; ++x) invP[P[x]] = x;
  A = N / B;
  solverP.build(P);
  solverInvP.build(invP);
  vector<int> cs(N);
  for (int x = 0; x < N; ++x) cs[x] = P[x] / B;
  // f[a0][a1][c]: inside [a0 B, a1 B) * [0, c B)
  for (int a0 = 0; a0 < A; ++a0) {
    for (int a = a0; a < A; ++a) {
      fill(f[a0][a + 1], f[a0][a + 1] + (A + 1), 0);
      for (int b = 0; b < B; ++b) {
        const int y = P[a * B + b];
        const int c = cs[a * B + b];
        // [a0 B, a B) * [0, y)
        f[a0][a + 1][c + 1] += (solverP.section[a][y] - solverP.section[a0][y]);
        // [a B, a B + b) * [0, y)
        f[a0][a + 1][c + 1] += solverP.inside[a][b][solverP.cntLess[a][y]];
      }
      for (int c = 0; c < A; ++c) {
        f[a0][a + 1][c + 1] += f[a0][a + 1][c];
      }
      for (int c = 0; c < A; ++c) {
        f[a0][a + 1][c + 1] += f[a0][a][c + 1];
      }
    }
  }
  // g[a][c0][c1]: [a B, (a+1) B) * [0, c0 B)  vs  [a B, (a+1) B) * [c0 B, c1 B)
  for (int a = 0; a < A; ++a) {
    for (int c0 = 0; c0 < A; ++c0) {
      fill(g[a][c0] + c0, g[a][c0] + (A + 1), 0);
      for (int b = 0; b < B; ++b) {
        const int c = cs[a * B + b];
        if (c0 <= c) {
          g[a][c0][c + 1] += solverP.inside[a][b][solverP.cntLess[a][c0 * B]];
        }
      }
      for (int c = c0; c < A; ++c) {
        g[a][c0][c + 1] += g[a][c0][c];
      }
    }
  }
}

Int calc(int x0, int x1, int y0, int y1) {
  assert(0 <= x0); assert(x0 <= x1); assert(x1 <= N);
  assert(0 <= y0); assert(y0 <= y1); assert(y1 <= N);
  Int ret = 0;
  ret += solverP.calc(x0, x1, y0, y1);
  const int a0 = x0 / B + 1;
  const int a1 = x1 / B;
#define x0 do_not_use_x0
#define x1 do_not_use_x1
  if (a0 < a1) {
    ret += solverInvP.calc(y0, y1, a0 * B, a1 * B);
    const int c0 = y0 / B + 1;
    const int c1 = y1 / B;
#define y0 do_not_use_y0
#define y1 do_not_use_y1
    if (c0 < c1) {
      ret += f[a0][a1][c1];
      ret -= f[a0][a1][c0];
      for (int a = a0; a < a1; ++a) {
        ret -= g[a][c0][c1];
      }
      for (int a = a0; a < a1; ++a) {
        // [a B, (a+1) B) * [0, c0 B)  vs  [(a+1) B, a1 B) * [c0 B, c1 B)
        ret -= (Int)(solverP.section[a + 1][c0 * B] - solverP.section[a][c0 * B]) *
            (Int)(solverP.section[a1][c1 * B] - solverP.section[a1][c0 * B] - solverP.section[a + 1][c1 * B] + solverP.section[a + 1][c0 * B]);
      }
    }
  }
  return ret;
}
#undef x0
#undef x1
#undef y0
#undef y1

int main() {
  int Q;
  for (; ~scanf("%d%d", &N, &Q); ) {
    P.resize(N);
    for (int x = 0; x < N; ++x) {
      scanf("%d", &P[x]);
      --P[x];
    }
    build();
    
#ifdef LOCAL
if(N<=10){
 for(int x0=0;x0<=N;++x0)for(int x1=x0;x1<=N;++x1)
 for(int y0=0;y0<=N;++y0)for(int y1=y0;y1<=N;++y1)
 {
  Int brt=0;
  {
   const int a0=x0/B+1;
   const int a1=x1/B;
   const int c0=y0/B+1;
   const int c1=y1/B;
   for(int x2=x0;x2<x1;++x2)for(int x3=x2+1;x3<x1;++x3)if(y0<=P[x2]&&P[x2]<P[x3]&&P[x3]<y1){
    // if(x2<a0*B||a1*B<=x3)++brt;
    // if(x2<a0*B||a1*B<=x3||P[x2]<c0*B||c1*B<=P[x3])++brt;
    ++brt;
   }
  }
  const Int ans=calc(x0,x1,y0,y1);
  if(brt!=ans)cerr<<P<<" ["<<x0<<", "<<x1<<") * ["<<y0<<", "<<y1<<"): "<<brt<<" "<<ans<<endl;
  assert(brt==ans);
 }
}
#endif
    
    for (int q = 0; q < Q; ++q) {
      int x0, x1, y0, y1;
      scanf("%d%d%d%d", &x0, &x1, &y0, &y1);
      --x0;
      --y0;
      const Int ans = calc(x0, x1, y0, y1);
      printf("%lld\n", ans);
    }
  }
  return 0;
}