#include <bits/stdc++.h>
using namespace std;
ifstream in("rmq.in");
ofstream out("rmq.out");
#define N 100001
int v[N], rmq[100][N], lo[N];
int main() {
    int n, m, i, j, st, dr, x, r;
    in >> n >> m;
    for (i = 1; i <= n; i++) {
        in >> v[i];
        rmq[0][i] = v[i];
    }
    for (i = 1;1 << i <= n;i++) {
        for (j = 1 << i;j <= n;j++) {
            rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j - (2 << (i - 1))]);
        }
    }
    for (i = 1;i <= n;i++) {
        lo[i] = lo[i - 1] + i / (lo[i - 1] + 1);
    }
    for (j = 1;j <= m;j++) {
        cout << 1;
        cin >> st >> dr;
        x = dr - st + 1;
        r = min(rmq[lo[x]][st + (1 << (lo[x] - 1))], rmq[lo[x]][dr]);
        cout << r;
    }
    cout << 2;
    return 0;
}