Description

Hint: Please note the constraints on $n$ and $q$ in this problem.

Let $\text{len}(a)$ denote the length of sequence $a$, and $a_{[l,r]}$ denote the subsequence of $a$ from index $l$ to $r$ inclusive.

Initially, Little L has an empty sequence $b$. Little L can perform the following operations in order several times to eventually transform $b$ into the target sequence $a$:

• Generate a sequence $c$ such that $\text{len}(b)\leq\text{len}(c)$.
• If there exists $1\leq i\leq\text{len}(b)$ such that $b_i=c_i$, then gain $1$ point; otherwise, gain $0$ points.
• Append sequence $c$ to the end of sequence $b$.

Little L wants to know, under the goal of achieving the target sequence, what is the maximum number of points that can be obtained. Let $f(a)$ be the answer to this problem when $a$ is the target sequence.

To prevent you from cheating Little L, Little L will first give you an array $a$ and then perform $q$ queries. Each query gives two integers $l, r$, and you need to answer the value of $f(a_{[l,r]})$.

Input Format

The first line contains two integers $n, q$, representing the length of sequence $a$ and the number of queries, respectively.

The second line contains $n$ non-negative integers $a_i$.

Then, $q$ lines follow, each with two integers $l, r$, representing the query interval.

Output Format

Output $q$ lines, each containing an integer, representing the value of $f(a_{[l,r]})$ for each query.

9 2
3 3 3 1 0 2 0 1 0
1 9
2 8

3
1

Hint

【Sample Explanation】

For the first query, the sequence is $a_{[1,9]}=\{3,3,3,1,0,2,0,1,0\}$. One possible way to achieve the maximum points is as follows:

• First operation: let $c=\{3\}$, gain $0$ points, now $b=\{3\}$.
• Second operation: let $c=\{3\}$, gain $1$ point, now $b=\{3,3\}$.
• Third operation: let $c=\{3,1\}$, gain $1$ point, now $b=\{3,3,3,1\}$.
• Fourth operation: let $c=\{0,2,0,1,0\}$, gain $1$ point, now $b=\{3,3,3,1,0,2,0,1,0\}$.

The total points gained is $3$. It can be proven that no scheme can gain more than $3$ points.

【Data Range】

This problem uses bundled tests.

• Special Constraint A: $a_i\leq50$.
• Special Constraint B: Each number in sequence $a$ appears at most $50$ times.

For all data, $1\leq n\leq10^6$, $1\leq q\leq50$, $1\leq l\leq r\leq n$, $1\leq a_i\leq n$.