Problem Description

Autumn and Bakser are studying Gty's girl sequence again, but they have run into a difficult problem.

Given a segment of girls, they want you to help compute the number of distinct beauty values whose beauty is in $\in [a,b]$ within this segment.

For convenience, we assume all beauty values are within $[1,n]$.

Given a positive integer sequence $s$ of length $n(1 \le n \le 10^5)$ with $s_i(1 \le s_i \le n)$, and $m(1 \le m \le 10^6)$ queries $l,r,a,b$, for each query output, in $s_l \cdots s_r$, the number of distinct values that are $\in [a,b]$.

Input Format

The first line contains two integers $n,m(1 \le n \le 100000,1 \le m \le 1000000)$, representing the number of elements in sequence $s$ and the number of queries.

The second line contains $n$ integers $s_1 \cdots s_n(1 \le s_i \le n)$.

The next $m$ lines each contain $4$ integers $l,r,a,b(1 \le l \le r \le n,1 \le a \le b \le n)$, with the meaning as described in the statement.

It is guaranteed that all numbers involved fit in C++ int. The input is guaranteed to be valid.

Output Format

For each query, output a single line representing, in $s_l \cdots s_r$, the number of distinct values that are $\in [a,b]$.

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

Hint

【Partial explanation of the sample】

5 9 1 2
The subsequence is 4 1 5 1 2.
The values within $[1,2]$ are 1, 1, 2. There are 2 distinct values, so the answer is 2.

3 4 7 9
The subsequence is 5 1.
The values within $[7,9]$ are 5. There is 1 distinct value, so the answer is 1.

4 4 2 5
The subsequence is 1.
There are no values within $[2,5]$, so the answer is 0.

2 3 4 7
The subsequence is 4 5.
The values within $[4,7]$ are 4, 5. There are 2 distinct values, so the answer is 2.

It is recommended to use input/output optimization.

Translated by ChatGPT 5