Counting Maximal Consecutive Value Segments

You are given a sequence of integers. For each query, you need to count the number of maximal consecutive value segments of lengths 1, 2, …, 10 in the value domain of the subarray.

A value-range consecutive segment is defined as follows:

• Extract the subarray for the given query and sort it while removing duplicates. Suppose after this process you obtain the sequence \(b_1, b_2, \ldots, b_m\).
• A pair \((l, r)\) (with \(1 \le l \le r \le m\)) forms a consecutive segment if for each index \(i\) from \(l\) to \(r-1\), \(b_{i+1} = b_i + 1\).
• The segment \((l, r)\) is maximal if neither \((l-1, r)\) nor \((l, r+1)\) (when defined) is a consecutive segment.

Your task is to output, for each query, 10 numbers. The i-th number (for \(i=1,2,\ldots,10\)) represents the number of maximal consecutive segments that have a length exactly equal to \(i\). If no such segment exists for some length, output 0 for that length.

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(q\) representing the size of the sequence and the number of queries.

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\), representing the sequence.

Each of the next \(q\) lines contains two integers \(L\) and \(R\) representing a query which asks about the subarray \(a_L, a_{L+1}, \ldots, a_R\) (1-indexed).

outputFormat

For each query, output a single line with 10 space-separated integers. The i-th integer should denote the number of maximal consecutive value segments in the query's subarray that have length exactly equal to \(i\) (for \(i=1,2,\ldots,10\)).

sample

5 2
1 2 4 3 5
1 5
2 4

0 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0