[Ynoi2015] 即便看不到未来

题目背景

![](https://cdn.luogu.com.cn/upload/pic/45556.png) 我不会再闷闷不乐了 那撕裂胸口的悲伤 还有快流下来的眼泪 全都是塑造出现在的我的东西 ![](https://cdn.luogu.com.cn/upload/pic/45557.png) 烦恼 灰心 痛苦 喜悦 全部不可或缺 现在站在这里的不是别人 ![](https://cdn.luogu.com.cn/upload/pic/45558.png) 毫无疑问是我自己,是珂朵莉 对,至少现在如此 ![](https://cdn.luogu.com.cn/upload/pic/45559.png) 记忆慢慢地缺失 人格在逐渐崩坏 抱歉 你们当中 已经有一半的人我不记得了... 忘记的名字还可以重新记住 但是失去的记忆却无可挽回 这个将要崩坏的自己,还能被称作珂朵莉吗...? ![](https://cdn.luogu.com.cn/upload/pic/45560.png) 可即便这样的感情,我也想要毫无保留地去珍惜 因为如果连这种感情都失去的时候 我大概就会...彻底消失吧

题目描述

珂朵莉给了你一个序列,每次查询一段区间中长度为 $1,2,\ldots,10$ 的极长值域连续段个数。 定义值域连续段为: * 把区间里面所有数排序后去重,设排序后得到的序列为 $b$。 * 如果对于二元组 $(l,r)$ 满足 $b_l,b_{l+1},\ldots,b_r$ 中每个数为前一个数 $+1$。 * 而且对于二元组 $(l,r+1)$,$(l-1,r)$ 均不满足,我们称 $(l,r)$ 为一个长度为 $r-l+1$ 的极长值域连续段。

输入输出格式

输入格式


第一行两个整数 $n,m$,表示序列的长度和查询的次数。 之后一行 $n$ 个整数表示这个序列。 之后 $m$ 行每行两个整数 $l,r$ 表示查询的区间。

输出格式


对于每次询问,输出一个长度为 $10$ 的字符串,第 $i$ 个字符表示长度为 $i$ 的极长连续段个数 $\bmod 10$的结果。

输入输出样例

输入样例 #1

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

输出样例 #1

1100000000
1000000000
1000000000
1000000000
0100000000
1000000000
2000000000
2000000000
1000000000

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:mcfx,Data:nzhtl1477 对于 $100\%$ 的数据,$1\leq n,m,a_i\leq10^6$,$1\leq l\leq r\leq n$。