#include<bits/stdc++.h>
#define N 1000050
using namespace std;
#define lowbit(x) (x & -x)
struct TT {
    int t[N];
    void update(int x, int y) {
        for(; x; x -= lowbit(x)) t[x] += y;
    }
    int query(int x) {
        int ret = 0;
        for(; x < N; x += lowbit(x)) ret += t[x];
        return ret;
    }
} t[13];
struct Q {
    int l, id;
} ;
vector<Q> q[N];
int pre[N], a[N], n, m, id[N], vis[N], ans[N][13];
int cmp(int x, int y) {
    return pre[x] > pre[y];
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i ++) {
        int l, r;
        scanf("%d%d", &l, &r);
        q[r].push_back((Q){l, i});
    }
    for(int r = 1; r <= n; r ++) {
        int ll = max(1, a[r] - 11), rr = a[r] + 11, gs = 0;
        for(int i = ll; i <= rr; i ++) if(pre[i] >= pre[a[r]]) id[++ gs] = i;
        sort(id + 1, id + 1 + gs, cmp);
        t[1].update(r, 1), t[1].update(pre[id[1]], -1);
        int L = 0, R = 0;
        for(int i = 1; i < gs; i ++) {
            vis[id[i]] = 1;
            while(vis[a[r] - L - 1]) L ++;
            while(vis[a[r] + R + 1]) R ++;
            int U = min(L + R + 1, 11);
            t[L].update(pre[id[i]], -1), t[L].update(pre[id[i + 1]], 1);
            t[R].update(pre[id[i]], -1), t[R].update(pre[id[i + 1]], 1);
            t[U].update(pre[id[i]], 1), t[U].update(pre[id[i + 1]], -1);
        }
        for(int i = ll; i <= rr; i ++) vis[i] = 0;
        for(int i = 0; i < q[r].size(); i ++)
            for(int j = 1; j <= 10; j ++)
                ans[q[r][i].id][j] = t[j].query(q[r][i].l);
        
        pre[a[r]] = r;
    }
    for(int i = 1; i <= m; i ++) {
        for(int j = 1; j <= 10; j ++) printf("%d", ans[i][j] % 10); printf("\n");
    }
    return 0;
}