Description

Ke Duoli gives you a sequence. For each query, you need to count, in a given interval, the number of maximal consecutive value-range segments of lengths $1,2,\ldots,10$.

A consecutive value-range segment is defined as follows:

• Sort all numbers in the interval and remove duplicates. Let the resulting sequence be $b$.
• For a pair $(l,r)$, if every number in $b_l,b_{l+1},\ldots,b_r$ is equal to the previous number $+1$.
• And for the pairs $(l,r+1)$ and $(l-1,r)$, neither satisfies the condition above, then we call $(l,r)$ a maximal consecutive value-range segment, with length $r-l+1$.

Input Format

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

The next line contains $n$ integers representing the sequence.

Then follow $m$ lines, each containing two integers $l,r$, representing the query interval.

Output Format

For each query, output a string of length $10$. The $i$-th character represents the number of maximal consecutive segments of length $i$ modulo $10$.

8 9
2 3 3 3 3 6 6 6
1 8
2 3
4 5
6 8
1 2
3 4
5 6
3 8
5 5

1100000000
1000000000
1000000000
1000000000
0100000000
1000000000
2000000000
2000000000
1000000000

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: mcfx, Data: nzhtl1477.

For $100\%$ of the testdata, $1\leq n,m,a_i\leq10^6$, $1\leq l\leq r\leq n$.

Translated by ChatGPT 5