Background

I will not be depressed anymore.
That sadness that tears open my chest,
and the tears that are about to fall,
are all things that shaped who I am now.

Worries,
discouragement,
pain,
joy,
none of them can be missing.
The one standing here now is not someone else.

Without a doubt, it is me myself, it is Ke Duoli (pinyin: Kē Duō Lí).
Yes, at least for now.

My memories are slowly disappearing,
and my personality is gradually falling apart.
Sorry.
Among you,
there are already half of you that I cannot remember...
Forgotten names can be remembered again,
but lost memories can never be recovered.
Can this self that is about to collapse still be called Ke Duoli...?

But even with feelings like this, I still want to cherish them without holding anything back.
Because if I lose even this kind of feeling,
I will probably... disappear completely.

Problem 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