#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100003;

const int M = 1000003;

void read(int &k) {

	k = 0; int fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 1) + (k << 3) + c - '0';

	k = k * fh;

}

struct node {int l, r, a, b, id;} Q[M];

int w[N], bel[N], n, m, sum[N], A[M], c[N];

bool cmp(node A, node B) {return bel[A.l] == bel[B.l] ? A.r < B.r : A.l < B.l;}

void update(int a, int flag) {

	c[a] += flag;

	if (flag == -1 && c[a] == 0) --sum[bel[a]];

	if (flag == 1 && c[a] == 1) ++sum[bel[a]];

}

int QQ(int l, int r) {

	int bl = bel[l], br = bel[r], ret = 0;

	if (bl == br) {

		for(int i = l; i <= r; ++i)

			if (c[i] > 0) ++ret;

		return ret;

	}

	for(int i = l; bel[i] == bel[l]; ++i)

		if (c[i] > 0) ++ret;

	for(int i = r; bel[i] == bel[r]; --i)

		if (c[i] > 0) ++ret;

	for(int i = bel[l] + 1; i < bel[r]; ++i)

		ret += sum[i];

	return ret;

}

int main() {

	read(n); read(m);

	for(int i = 1; i <= n; ++i) read(w[i]);

	for(int i = 1; i <= m; ++i) {read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id = i;}

	int t = sqrt(n + 0.5), cnt = 1, tmp = 1;

	for(int i = 1; i <= n; ++i) {

		bel[i] = tmp;

		++cnt; if (cnt > t) {cnt = 1; ++tmp;}

	}

	sort(Q + 1, Q + m + 1, cmp);

	int l = 1, r = 0, tol, tor;

	for(int i = 1; i <= m; ++i) {

		tol = Q[i].l; tor = Q[i].r;

		while (l < tol) update(w[l++], -1);

		while (l > tol) update(w[--l], 1);

		while (r < tor) update(w[++r], 1);

		while (r > tor) update(w[r--], -1);

		A[Q[i].id] = QQ(Q[i].a, Q[i].b);

	}

	for(int i = 1; i <= m; ++i) printf("%d\n", A[i]);

	return 0;

}