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

const int N = 1e6 + 10;
int n, m;
int a[N];
LL ans[N];

struct Node {
	long double tag; // 历史未处理的求和次数
	LL sum, val; // 历史和，区间和
	int lazy, len; // 区间赋值懒标记，区间长度
	void cl(int t) { // 区间赋值的标记合并
		tag = tag * lazy * 1.0 / t;
		lazy = t, val = t * len;
	} void addc(long double lt) { // 区间历史求和次数的标记合并
		tag += lt;
		sum += val * lt;
	}
} tr[N << 2];

void pushdown(int u) {
	if (tr[u].lazy) {
		tr[u << 1].cl(tr[u].lazy);
		tr[u << 1 | 1].cl(tr[u].lazy);
		tr[u].lazy = 0;
	} if (tr[u].tag) {
		tr[u << 1].addc(tr[u].tag);
		tr[u << 1 | 1].addc(tr[u].tag);
		tr[u].tag = 0;
	}
}

void build(int u, int l, int r) {
	tr[u].len = r - l + 1;
	if (l == r) return;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 
}

void modify(int u, int l, int r, int s, int t, int k) {
	if (s <= l && r <= t) {
		tr[u].cl(k);
		return;
	}
	pushdown(u);
	int mid = l + r >> 1;
	if (s <= mid) modify(u << 1, l, mid, s, t, k);
	if (t > mid) modify(u << 1 | 1, mid + 1, r, s, t, k);
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

LL query(int u, int l, int r, int s, int t) {
	if (s > t) return 0;
	if (s <= l && r <= t) return tr[u].sum;
	pushdown(u);
	int mid = l + r >> 1;
	LL res = 0;
	if (s <= mid) res += query(u << 1, l, mid, s, t);
	if (t > mid) res += query(u << 1 | 1, mid + 1, r, s, t);
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
	vector<vector<pair<pair<int, int>, int>>> Q(n + 1);
	for (int i = 1; i <= m; i ++ ) {
		int x, y, l, r;
		scanf("%d%d%d%d", &x, &y, &l, &r);
		Q[r].push_back({{y, i}, 1});
		Q[r].push_back({{x - 1, i}, -1});
		Q[l - 1].push_back({{y, i}, -1});
		Q[l - 1].push_back({{x - 1, i}, 1});
	}
	build(1, 1, n);
	set<int> se;
	se.insert(0);
	unordered_map<int, int> la;
	for (int i = 1; i <= n; i ++ ) {
		int x = la[a[i]];
		se.insert(i);
		if (x) {
			auto it = se.find(x);
			int pre, suf;
			pre = *--it , it ++ ;
			suf = *++it , it -- ;
			modify(1, 1, n, pre + 1, x, suf);
			se.erase(it);
		}
		modify(1, 1, n, (*--(--se.end())) + 1, i, i);
		la[a[i]] = i;
		tr[1].addc(1);
		for (auto t : Q[i]) ans[t.first.second] += query(1, 1, n, 1, t.first.first) * t.second;
	}
	for (int i = 1; i <= m; i ++ ) printf("%lld\n", ans[i]);
	return 0;
}