100 1
100 50 99 49 98 48 97 47 96 46 95 45 94 44 93 43 92 42 91 41 90 40 89 39 88 38 87 37 86 36 85 35 84 34 83 33 82 32 81 31 80 30 79 29 78 28 77 27 76 26 75 25 74 24 73 23 72 22 71 21 70 20 69 19 68 18 67 17 66 16 65 15 64 14 63 13 62 12 61 11 60 10 59 9 58 8 57 7 56 6 55 5 54 4 53 3 52 2 51 1
9 8 99 93
 2 9
1 2
1 1 1 1
1 1 1 2
1 2 1 2
1 1 2 1
1 1 2 2
1 2 2 2
2 1 2 1
2 1 2 2
2 2 2 2
 10 10
6 5 7 4 8 3 9 2 10 1
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
1 10 2 9 3 8 4 7 5 6
4 3 7 10
3 6 8 7
3 2 6 4
1 1 2 8
3 8 10 9
7 3 8 9
4 5 5 9
2 5 6 7
2 5 6 7
1 7 6 10
 10 5
5 10 4 9 3 8 2 7 1 6
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
10 9 8 7 6 5 4 3 2 1
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 7 7
1 2 3 6 7 4 5
3 2 4 6
3 2 5 4
3 6 7 7
1 1 4 4
2 2 7 6
1 2 6 2
1 2 6 7
 10 10
6 1 7 2 8 3 9 4 10 5
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
5 1 6 2 8 3 4 10 9 7
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
5 6 4 7 3 8 2 9 1 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
10 5 9 4 8 3 7 2 6 1
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
7 5 1 6 10 3 4 8 9 2
4 3 7 10
3 6 8 7
3 2 6 4
1 1 2 8
3 8 10 9
7 3 8 9
4 5 5 9
2 5 6 7
2 5 6 7
1 7 6 10
 10 10
1 2 3 4 5 6 7 8 9 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
5 1 6 2 8 3 4 10 9 7
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
9 8 3 4 5 6 7 2 1 10
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
10 1 9 2 8 3 7 4 6 5
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
5 1 6 2 8 3 4 10 9 7
9 5 9 5
4 7 4 7
4 8 5 8
9 1 9 4
4 1 4 6
10 9 10 9
3 5 6 5
3 4 10 4
3 2 5 2
7 8 7 8
 6 10
3 6 1 2 5 4
2 6 2 6
2 3 2 5
6 2 6 2
1 5 1 5
3 5 3 5
2 2 2 4
2 4 5 4
5 4 5 4
1 5 6 5
6 2 6 2
 10 10
1 6 2 7 3 8 4 9 5 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10

                                                            4886
                                                                1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               11
                                                              17
                                                              15
                                                               6
                                                              16
                                                               2
                                                              19
                                                               4
                                                              20
                                                               8
                                                               39
                                                              30
                                                              26
                                                              16
                                                              23
                                                              29
                                                              27
                                                              30
                                                              30
                                                              27
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                9
                                                              14
                                                              21
                                                              16
                                                              16
                                                               9
                                                              15
                                                               4
                                                              20
                                                               3
                                                               17
                                                              16
                                                              11
                                                              16
                                                              21
                                                              11
                                                              21
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                3
                                                               8
                                                              37
                                                              27
                                                              21
                                                              38
                                                              29
                                                              21
                                                              23
                                                              24
                                                               16
                                                              17
                                                              12
                                                               6
                                                              16
                                                               2
                                                              23
                                                               4
                                                              20
                                                               8
                                                                8
                                                              10
                                                              38
                                                              26
                                                              21
                                                              38
                                                              31
                                                              20
                                                              21
                                                              19
                                                               38
                                                              30
                                                              25
                                                              17
                                                              24
                                                              28
                                                              29
                                                              32
                                                              32
                                                              25
                                                               23
                                                              17
                                                              12
                                                               6
                                                              27
                                                               2
                                                              23
                                                               7
                                                              24
                                                               8
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                8
                                                              14
                                                              38
                                                              27
                                                              19
                                                              38
                                                              29
                                                              20
                                                              23
                                                              19
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                               10
                                                              16
                                                              17
                                                               8
                                                              27
                                                               2
                                                              25
                                                              26
                                                              16
                                                              16
                                                                5
                                                               9
                                                               2
                                                               2
                                                               6
                                                               8
                                                              11
                                                               8
                                                               9
                                                               2
                                                               16
                                                              17
                                                              12
                                                               6
                                                              16
                                                               2
                                                              23
                                                               7
                                                              18
                                                               8

#include <bits/stdc++.h>
using namespace std;
int p[200200], pr[200200];
int ql[200200], qr[200200], qt[200200], qb[200200];
unordered_map<int, unordered_map<int, int>> isord;
unordered_map<int, unordered_map<int, int>> sol;
vector<pair<int, int>> ord;
const int mx = (1 << 18);
int tree[2 * mx];
void update(int i) {
  while (i >>= 1) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}
int query(int i, int u, int v, int l, int r) {
  if (l <= u && v <= r) {
    return tree[i];
  }
  int mid = (u + v) / 2, ans = 0;
  if (l < mid) ans += query(i << 1, u, mid, l, r);
  if (mid < r) ans += query(i << 1 | 1, mid, v, l, r);
  return ans;
}
void put(int r, int c) {
  if (r > 0 && c > 0 && !isord[r][c]) {
    isord[r][c] = 1;
    ord.push_back(make_pair(r, c));
  }
}
int main() {
  int n, q;
  scanf("%d%d", &(n), &(q));
  for (int i = 1; i <= n; i++) {
    scanf("%d", &(p[i]));
    pr[p[i]] = i;
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &(ql[i]), &(qt[i]));
    scanf("%d%d", &(qr[i]), &(qb[i]));
    put(qb[i], ql[i] - 1);
    put(qt[i] - 1, qr[i]);
    put(qb[i], qr[i]);
    put(qt[i] - 1, ql[i] - 1);
  }
  sort(ord.begin(), ord.end());
  int j = 0;
  for (int ro = 1; ro <= n; ro++) {
    tree[mx + pr[ro]] = 1;
    update(mx + pr[ro]);
    while (j < ord.size() && ord[j].first < ro) j++;
    while (ord[j].first == ro) {
      int qans = query(1, mx, mx << 1, mx + 1, mx + ord[j].second + 1);
      sol[ord[j].first][ord[j].second] = qans;
      j++;
    }
  }
  for (int i = 1; i <= q; i++) {
    int r = qr[i], l = ql[i], t = qt[i], b = qb[i];
    long long ins =
        sol[b][r] - sol[b][l - 1] - sol[t - 1][r] + sol[t - 1][l - 1];
    long long ans = ins * (n - ins) + ins * (ins - 1) / 2;
    vector<int> x;
    x.push_back(sol[t - 1][l - 1]);
    x.push_back(sol[t - 1][r] - sol[t - 1][l - 1]);
    x.push_back(t - 1 - sol[t - 1][r]);
    x.push_back(sol[b][l - 1] - sol[t - 1][l - 1]);
    x.push_back(b - sol[b][r] - (t - 1) + sol[t - 1][r]);
    x.push_back(l - 1 - sol[b][l - 1]);
    x.push_back(r - (l - 1) - sol[b][r] + sol[b][l - 1]);
    x.push_back(n - r - b + sol[b][r]);
    long long ans2 = 0;
    ans2 += 1LL * x[0] * (x[4] + x[6] + x[7]);
    ans2 += 1LL * x[1] * (n - (t - 1) - ins);
    ans2 += 1LL * x[2] * (x[3] + x[5] + x[6]);
    ans2 += 1LL * x[3] * (n - (l - 1) - ins);
    ans2 += 1LL * x[4] * (r - ins);
    ans2 += 1LL * x[5] * (x[1] + x[2] + x[4]);
    ans2 += 1LL * x[6] * (b - ins);
    ans2 += 1LL * x[7] * (x[0] + x[1] + x[3]);
    ans += ans2 / 2;
    printf(
        "%lld"
        "\n",
        ans);
  }
  return 0;
}
