Description

You are given a string $a$. For each query, you are asked about the contribution of a sub-interval.

Definition of contribution:

Each time, pick a character $x$ from this interval (the order is up to you), then delete $x$ from the interval. Repeat until the interval is empty. You need to maintain a set $S$.

• If $S$ is empty, your rp decreases by $1$.
• If there exists an element in $S$ that is not less than $x$, then your rp decreases by $1$, and you clear $S$.
• After that, insert $x$ into $S$.

Since you are the boss, problems you have done usually appear in exams. After you process all characters in this interval, what is the maximum rp you can still have? The initial rp is $0$.

Queries are independent.

Input Format

The first line contains two integers $n, m$, the length of the string and the number of queries.

The next line contains $n$ numbers. The $i$-th integer is the $i$-th character $a_i$ of the given string.

Then $m$ lines follow. Each line contains two integers $l, r$, meaning a query interval.

Output Format

For each query, output a single integer on one line representing the answer.

3 3
3 3 3
3 3
3 3
3 3

-1
-1
-1

Hint

Constraints

• For $10\%$ of the testdata, they are the sample.
• For another $10\%$ of the testdata, $n, m \le 100$.
• For another $10\%$ of the testdata, $n, m \le 10^3$.
• For another $10\%$ of the testdata, $n, m \le 10^4$.
• For another $10\%$ of the testdata, $n, m \le 10^5$.
• For $100\%$ of the testdata, $1 \leq n, m \le 2 \times 10^5$, $1 \leq a_i \leq 10^9$, $1 \leq l, r \leq n$.

The testdata is as easy as a certain province’s NOI Qualifier Day 1 T2. Feel free to pass it with brute force.

It’s okay. As long as you are in a good school, even if you can only get 10 points on this problem, you can still make the team.

Translated by ChatGPT 5