#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const short SqrtN = 409,SIZE = 1 << 14;
inline char gc(){
static char buf[SIZE],*t1 = buf,*t2 = buf;
return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,SIZE,stdin),t1 == t2) ? EOF : *t1++;
}
int read(){
char c = gc();
int x = 0;
while(c < '0' || c > '9')
c = gc();
while(c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + c - 48;
c = gc();
}
return x;
}
int n,m;
struct node{
int num,id;
} a[N],tmp[N];
bool cmp(const node x,const node y){
return x.num < y.num;
}
short block_cnt,block_len;
struct block{
int l,r;
} b[SqrtN];
short belong[N];
short p[N][SqrtN];
int pre[SqrtN][N];
int ans1[SqrtN][SqrtN][SqrtN];
int ans2[SqrtN][SqrtN][SqrtN];
int query1(const int l,const int r,const int x,const int y){
const short pos = belong[l];
int ret = 0;
for(int i = l;i <= r;i++)
if(a[i].num >= x && a[i].num <= y){
ret += p[i][pre[pos][a[i].num - 1] - pre[pos - 1][a[i].num - 1]] - p[i][pre[pos][x - 1] - pre[pos - 1][x - 1]];
if(l != b[pos].l)
ret -= p[l - 1][pre[pos][a[i].num - 1] - pre[pos - 1][a[i].num - 1]] - p[l - 1][pre[pos][x - 1] - pre[pos - 1][x - 1]];
}
return ret;
}
int tmp1[N];short top1;
int tmp2[N];short top2;
long long query2(const int l,const int r,const int x,const int y){
const short pos_l = belong[l],pos_r = belong[r];
const int l_l = b[pos_l].l,l_r = b[pos_l].r;
const int r_l = b[pos_r].l,r_r = b[pos_r].r;
long long ret = 0;
for(int i = l;i <= l_r;i++)
if(a[i].num >= x && a[i].num <= y){
ret += p[i][pre[pos_l][a[i].num - 1] - pre[pos_l - 1][a[i].num - 1]] - p[i][pre[pos_l][x - 1] - pre[pos_l - 1][x - 1]];
if(l != l_l)
ret -= p[l - 1][pre[pos_l][a[i].num - 1] - pre[pos_l - 1][a[i].num - 1]] - p[l - 1][pre[pos_l][x - 1] - pre[pos_l - 1][x - 1]];
}
for(int i = r_l;i <= r;i++)
if(a[i].num >= x && a[i].num <= y)
ret += p[i][pre[pos_r][a[i].num - 1] - pre[pos_r - 1][a[i].num - 1]] - p[i][pre[pos_r][x - 1] - pre[pos_r - 1][x - 1]];
top1 = top2 = 0;
for(int i = l_l;i <= l_r;i++)
if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
tmp1[++top1] = tmp[i].num;
for(int i = r_l;i <= r_r;i++)
if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
tmp2[++top2] = tmp[i].num;
short i = 1,j = 1;
while(i <= top1 && j <= top2){
if(tmp1[i] < tmp2[j]){
i++;
ret += top2 - j + 1;
}
else
j++;
}
for(int i = l_l;i <= l_r;i++)
if(tmp[i].id >= l && tmp[i].num >= x && tmp[i].num <= y)
ret += (pre[pos_r - 1][y] - pre[pos_r - 1][tmp[i].num]) - (pre[pos_l][y] - pre[pos_l][tmp[i].num]);
for(int i = r_l;i <= r_r;i++)
if(tmp[i].id <= r && tmp[i].num >= x && tmp[i].num <= y)
ret += (pre[pos_r - 1][tmp[i].num] - pre[pos_r - 1][x - 1]) - (pre[pos_l][tmp[i].num] - pre[pos_l][x - 1]);
for(short i = pos_l + 1;i <= pos_r - 1;i++)
ret += ans2[i][pre[i][x - 1] - pre[i - 1][x - 1] + 1][pre[i][y] - pre[i - 1][y]];
for(short i = pos_l + 1;i <= pos_r - 1;i++)
ret += (ans1[i][i - 1][pre[i][y] - pre[i - 1][y]] - ans1[i][i - 1][pre[i][x - 1] - pre[i - 1][x - 1]]) - (ans1[i][pos_l][pre[i][y] - pre[i - 1][y]] - ans1[i][pos_l][pre[i][x - 1] - pre[i - 1][x - 1]]);
int temp = 0;
for(short i = pos_l + 1;i <= pos_r - 1;i++){
ret -= 1ll * temp * ((pre[i][y] - pre[i - 1][y]) - (pre[i][x - 1] - pre[i - 1][x - 1]));
temp += pre[i][x - 1] - pre[i - 1][x - 1];
}
return ret;
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);
n = read();m = read();
for(int i = 1;i <= n;i++)
tmp[i] = a[i] = (node){read(),i};
block_len = 317;
block_cnt = (n + block_len - 1) / block_len;
for(short i = 1;i <= block_cnt;i++){
b[i].l = b[i - 1].r + 1;
b[i].r = b[i].l + block_len - 1;
}
b[block_cnt].r = n;
for(short i = 1;i <= block_cnt;i++)
for(int j = b[i].l;j <= b[i].r;j++)
belong[j] = i;
for(short i = 1;i <= block_cnt;i++){
const int l = b[i].l,r = b[i].r;
sort(tmp + l,tmp + r + 1,cmp);
}
for(short i = 1;i <= block_cnt;i++){
const int l = b[i].l,r = b[i].r;
const short len = r - l + 1;
for(int j = l;j <= r;j++)
p[tmp[j].id][j - l + 1] = 1;
for(int j = l;j <= r;j++){
for(short k = 1;k <= len;k++){
if(j > l)
p[j][k] += p[j][k - 1] + p[j - 1][k] - p[j - 1][k - 1];
else
p[j][k] += p[j][k - 1];
}
}
}
for(short i = 1;i <= block_cnt;i++){
for(int j = b[i].l;j <= b[i].r;j++)
pre[i][a[j].num] = 1;
for(int j = 1;j <= n;j++)
pre[i][j] = pre[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
}
for(short i = 1;i <= block_cnt;i++){
const short len = b[i].r - b[i].l + 1;
for(short j = 1;j < i;j++)
for(short k = 1;k <= len;k++)
ans1[i][j][k] = ans1[i][j][k - 1] + pre[j][tmp[k + b[i].l - 1].num];
}
for(short i = 1;i <= block_cnt;i++){
const int l = b[i].l;
const short len = b[i].r - l + 1;
for(short j = 1;j < len;j++)
for(short k = j + 1;k <= len;k++)
ans2[i][j][k] = ans2[i][j][k - 1] + p[tmp[l + k - 1].id][k - 1] - p[tmp[l + k - 1].id][j - 1];
}
while(m--){
const int x1 = read(),x2 = read(),y1 = read(),y2 = read();
if(belong[x1] == belong[x2])
cout << query1(x1,x2,y1,y2) << '\n';
else
cout << query2(x1,x2,y1,y2) << '\n';
}
return 0;
}