Gty的二逼妹子序列

题目描述

Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。 对于一段妹子们,他们想让你帮忙求出这之内美丽度$\in [a,b]$的妹子的美丽度的种类数。 为了方便,我们规定妹子们的美丽度全都在$[1,n]$中。 给定一个长度为$n(1 \le n \le 100000)$的正整数序列$s(1 \le si \le n)$,对于$m(1 \le m \le 1000000)$次询问`l,r,a,b`,每次输出$s_l \cdots s_r$中,权值$\in [a,b]$的权值的种类数。

输入输出格式

输入格式


第一行包括两个整数$n,m(1 \le n \le 100000,1 \le m \le 1000000)$,表示数列$s$中的元素数和询问数。 第二行包括$n$个整数$s1…sn(1 \le si \le n)$。 接下来$m$行,每行包括$4$个整数$l,r,a,b(1 \le l \le r \le n,1 \le a \le b \le n)$,意义见题目描述。 保证涉及的所有数在C++的int内。保证输入合法。

输出格式


对每个询问,单独输出一行,表示$s_l \cdots s_r$中权值$\in [a,b]$的权值的种类数。

输入输出样例

输入样例 #1

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

输出样例 #1

2
0
0
2
1
1
1
0
1
2

说明

【样例的部分解释】 `5 9 1 2 ` 子序列为`4 1 5 1 2` 在[1,2]里的权值有1,1,2,有2种,因此答案为2。 `3 4 7 9` 子序列为`5 1 ` 在[7,9]里的权值有5,有1种,因此答案为1。 `4 4 2 5` 子序列为`1` 没有权值在[2,5]中的,因此答案为0。 `2 3 4 7` 子序列为`4 5` 权值在[4,7]中的有4,5,因此答案为2。 建议使用输入/输出优化。