题目描述

给定一个序列 $a_{1\cdots n}$，$m$ 次询问值域在 $[a,b]$ 内的数，在区间 $[l,r]$ 中出现了多少种。

输入格式

第一行两个整数 $n,m$。

接下来一行 $n$ 个数，表示 $a_{1\cdots n}$。

接下来 $m$ 行，每行四个整数 $l,r,a,b$ 表示一组询问。

输出格式

共 $m$ 行，每行一个整数表示对应询问的答案。

10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4

2
0
0
2
1
1
1
0
1
2

数据规模与约定

对于 $100\%$ 的数据，$1\leq a_i\leq n\leq 10^5$，$1\leq l\leq r\leq n$，$1\leq a\leq b\leq n$。