Distinct Beauty Count in Subsequence

Autumn and Bakser are once again studying Gty's beauty sequence. However, they have encountered a difficult problem.

Given a sequence of beauties where each beauty is in the range \( [1, n] \), you are asked to answer \( m \) queries. For each query, you are given four integers \( l, r, a, b \). The query asks you to find, among the subarray \( s_l, s_{l+1}, \ldots, s_r \), how many distinct beauty values fall within the interval \( [a, b] \).

Note: \( 1 \le s_i \le n \) for all \( i \).

inputFormat

The first line contains two integers \( n \) and \( m \) \( (1 \le n \le 10^5,\ 1 \le m \le 10^6) \), representing the length of the beauty sequence and the number of queries.

The second line contains \( n \) integers \( s_1, s_2, \ldots, s_n \) where \( 1 \le s_i \le n \).

Each of the following \( m \) lines contains four integers \( l, r, a, b \) representing a query. Here, \( l \) and \( r \) denote the segment \( s_l \) to \( s_r \), and \( [a, b] \) is the interval of beauty values.

outputFormat

For each query, output a single integer on a new line denoting the count of distinct beauty values from the subarray \( s_l, s_{l+1}, \ldots, s_r \) that lie within the range \( [a, b] \).

sample

5 3
1 2 3 2 1
1 5 1 3
2 4 2 2
3 5 1 2

3
1
2