不知道为什么穿成 SB 了，自己拿标拍了下随机数据都没挂，调不出来了……

/*
感觉自己再怎么写常数都会很大（
当然题解那个常数……我不知道说什么了
直接往左右两边扩展的常数应该是最小的 
*/
#include "bits/stdc++.h"
using namespace std;
const int Len = 4e6 + 5;
inline int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int n,m,lst[Len],a[Len],maxv;
struct node
{
	int c[Len];
	int lowbit(int x){return x & (-x);}
	void add(int x,int d){while(x <= n) c[x] += d , x += lowbit(x);}
	void upd(int l,int r,int w)
	{
		add(l , w);
		add(r + 1 , -w);
	}
	int qry(int x)
	{
		int res = 0;
		while(x) 
		{
			res += c[x];
			x -= lowbit(x);
		}
		return res;
	}
}t[23];
struct Node
{
	int x,id;
	Node(){x = id = 0;}
	Node(int X,int ID){x = X , id = ID;}
};
vector<Node> v[Len];
int Print[Len][11];
int main()
{
	n = read() , m = read();
	for(int i = 1 ; i <= n ; i ++) 
	{
		a[i] = read();
		maxv = max(maxv , a[i]);
	}
	int l,r;
	for(int i = 1 ; i <= m ; i ++)
	{
		l = read() , r = read();
		v[r].push_back(Node(l , i));
	}
	memset(lst , -1 , sizeof lst);
	for(int i = 1 ; i <= n ; i ++)
	{
		//printf("###%d\n",i);
		int idxl = a[i] - 1 , idxr = a[i] + 1 , maxnl = lst[idxl] , maxnr = lst[idxr];
		int lim = lst[a[i]] , lstr = i , lstL = 0 , lstR = 0 , len = 0;
		while(1)
		{
			if((idxl < 1 && idxr > maxv) || (a[i] - idxl + 1 > 11 && idxr - a[i] + 1 > 11) || (maxnl == -1 && maxnr == -1)) break;//如果已经走到边界或不可能产生指定范围的滑动块或或两边需要再扩展的数都没了或当前要扩展的数已经超过lstai了  
			if(maxnl > maxnr)//扩展左边
			{
				if(maxnl < lim) break;
				len = lstL + lstR + 1;
				//printf("!!!%d %d %d %d %d\n",maxnl + 1,lstr,lstL,lstR,len);
				if(1 <= lstL && lstL <= 10) t[lstL].upd(maxnl + 1 , lstr , -1);
				if(1 <= lstR && lstR <= 10) t[lstR].upd(maxnl + 1 , lstr , -1);
				if(1 <= len && len <= 10) t[len].upd(maxnl + 1 , lstr , 1);
				lstr = maxnl;
				maxnl = min(maxnl , lst[-- idxl]);
				if(lst[idxl] == -1) maxnl = lst[idxl];
				lstL ++;
			} 
			else
			{
				if(maxnr < lim) break;
				len = lstL + lstR + 1;
			//	printf("%d %d %d %d %d\n",maxnr + 1,lstr,lstL,lstR,len);
				if(1 <= lstL && lstL <= 10) t[lstL].upd(maxnr + 1 , lstr , -1);
				if(1 <= lstR && lstR <= 10) t[lstR].upd(maxnr + 1 , lstr , -1);
				if(1 <= len && len <= 10) t[len].upd(maxnr + 1 , lstr , 1);
				lstr = maxnr;
				maxnr = min(maxnr , lst[++ idxr]);
				if(lst[idxr] == -1) maxnr = lst[idxr]; 
				lstR ++;
			}
		}
		if(lst[a[i]] < lstr)
		{	
			len = lstL + lstR + 1;
			int x = (lst[a[i]] == -1) ? 1 : lst[a[i]] + 1;
			if(1 <= lstL && lstL <= 10) t[lstL].upd(x , lstr , -1);
			if(1 <= lstR && lstR <= 10) t[lstR].upd(x , lstr , -1);
			if(1 <= len && len <= 10) t[len].upd(x , lstr , 1);
		}
		for(int j = 0 ; j < v[i].size() ; j ++) 
			for(int k = 1 ; k <= 10 ; k ++) Print[v[i][j].id][k] = t[k].qry(v[i][j].x);
		lst[a[i]] = i;
	}
	for(int i = 1 ; i <= m ; i ++) 
	{
		for(int j = 1 ; j <= 10 ; j ++) write((Print[i][j] + 10) % 10);
		puts("");
	}
	return 0;
}