Gty 的妹子序列

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数序列 $s$，所有元素均在 $[1,n]$ 内。

每个询问给出 $l,r,a,b$，求子序列 $s_l,s_{l+1},\ldots,s_r$ 中，数值位于 $[a,b]$ 的不同整数种类数。

输入格式

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

第二行输入 $n$ 个整数 $s_1,s_2,\ldots,s_n$。

接下来 $m$ 行，每行输入四个整数 $l,r,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

数据范围

对于所有数据，$1\le n\le10^5$，$1\le m\le10^6$，$1\le s_i\le n$，$1\le l\le r\le n$，$1\le a\le b\le n$。