#include<algorithm>
#include<vector>
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const unsigned U1=-1;
namespace fastread{
	char C[(int)1e8],*buf=C;
	inline void init(){C[fread(C,1,(int)1e8-1,stdin)]='\n';fclose(stdin);}
	inline int readint(){
		int d=0;
		while(!isdigit(*buf))++buf;
		while(isdigit(*buf))d=d*10+(*buf++^'0');
		return d;
	}
}
char FW[(int)2e7],*buf=FW;
const int N=1e6+5;
int n,m,a[N],pre[N],ans[N][11];
bool vis[N];
vector<LL>num,vec[N];
int b[11][N];
inline void add(int i,int x,const int&p){for(;i<=n;i+=i&-i)b[p][i]+=x;}
inline int ask(int i,const int&p){int x=0;for(;i;i^=i&-i)x+=b[p][i];return x;}
inline void modify(int l,int r,int x,const int&p){add(l,x,p),add(r+1,-x,p);}
int main(){
	fastread::init();
	n=fastread::readint(),m=fastread::readint();
	for(int i=1;i<=n;++i)a[i]=fastread::readint();
	for(int i=1;i<=m;++i){
		int l=fastread::readint(),r=fastread::readint();
		vec[r].push_back((LL)l<<32|i);
	}
	for(int it=1;it<=n;++it){
		const int v=a[it],mn=max(1,v-11),mx=min(1000000,v+11);
		num.clear();
		for(int i=mn;i<=mx;++i)
			if(pre[i]&&pre[i]>pre[v])num.push_back((LL)pre[i]<<32|i);
		num.push_back((LL)it<<32|v),num.push_back((LL)pre[v]<<32|1000002);
		sort(num.rbegin(),num.rend());
		for(int i=0;i<num.size()-1;++i){
			int l=0,r=0;
			vis[num[i]&U1]=1;
			while(v-l-1&&l<=10&&vis[v-l-1])++l;
			while(v+r+1<=1000000&&r<=10&&vis[v+r+1])++r;
			const int all=l+r+1;
			if(l&&l<=10)modify((num[i+1]>>32)+1,num[i]>>32,-1,l);
			if(r&&r<=10)modify((num[i+1]>>32)+1,num[i]>>32,-1,r);
			if(all<=10)modify((num[i+1]>>32)+1,num[i]>>32,1,all);
		}
		pre[v]=it;
		for(int i:num)vis[i]=0;
		for(LL i:vec[it])
			for(int j=1;j<=10;++j)
				ans[i&U1][j]=ask(i>>32,j)%10;
	}
	for(int i=1;i<=m;++i,*buf++='\n')
		for(int j=1;j<=10;++j)
			*buf++=ans[i][j]^'0';
	fwrite(FW,1,buf-FW,stdout);
	return 0;
}