#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 16) + 5;
int n, q, blng[N], L[N], R[N], ID, cnt, Q[N], X[N], res[N];
map<pair<int, pair<int, int> >, int> Set;
vector<pair<int, int> > opt;
struct node {
  int x, y, w, p, id;
} cur[N];
inline bool cmpy(const node &fir, const node &sec) { return fir.y < sec.y; }
inline bool cmpx(const node &fir, const node &sec) { return fir.x < sec.x; }
int Merge(int a, int b) {
  opt.push_back(make_pair(a, b));
  return ++cnt;
}
int Solve(int l, int r, int w) {
  if (l == r) {
    cur[l].w = w;
    cur[l].p = l;
    return cur[l].id;
  }
  int mid = l + r >> 1;
  int ls = Solve(l, mid, 0);
  int rs = Solve(mid + 1, r, 1);
  ID++;
  sort(cur + l, cur + r + 1, cmpx);
  for (int i = l; i <= r; i++) {
    int Lmn = -1, Lmx = -1, Rmn = -1, Rmx = -1;
    for (int j = i; j <= r; j++) {
      if (cur[j].w == 0) {
        if (Lmn == -1) Lmn = cur[j].p;
        if (Lmx == -1) Lmx = cur[j].p;
        Lmn = min(Lmn, cur[j].p);
        Lmx = max(Lmx, cur[j].p);
      } else {
        if (Rmn == -1) Rmn = cur[j].p;
        if (Rmx == -1) Rmx = cur[j].p;
        Rmn = min(Rmn, cur[j].p);
        Rmx = max(Rmx, cur[j].p);
      }
      if (Lmn == -1)
        Set[make_pair(ID, make_pair(i, j))] =
            Set[make_pair(rs, make_pair(Rmn, Rmx))];
      else if (Rmn == -1)
        Set[make_pair(ID, make_pair(i, j))] =
            Set[make_pair(ls, make_pair(Lmn, Lmx))];
      else
        Set[make_pair(ID, make_pair(i, j))] =
            Merge(Set[make_pair(ls, make_pair(Lmn, Lmx))],
                  Set[make_pair(rs, make_pair(Rmn, Rmx))]);
    }
  }
  for (int i = l; i <= r; i++) cur[i].w = w, cur[i].p = i;
  return ID;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &cur[i].y);
    cur[i].x = cur[i].id = i;
  }
  cnt = ID = n;
  sort(cur + 1, cur + n + 1, cmpy);
  for (int i = 1; i <= n; i++)
    Set[make_pair(cur[i].id, make_pair(i, i))] = cur[i].id;
  int sz = (int)sqrt(q);
  for (int i = 1; i <= n; i++) {
    blng[i] = (i - 1) / sz + 1;
    if (blng[i] != blng[i - 1]) L[blng[i]] = i, R[blng[i - 1]] = i - 1;
  }
  R[blng[n]] = n;
  for (int i = 1; i <= blng[n]; i++) Q[i] = Solve(L[i], R[i], 0);
  for (int i = 1; i <= n; i++) X[i] = cur[i].x;
  for (int qry = 1; qry <= q; qry++) {
    int ql, qr, ans = -1;
    scanf("%d %d", &ql, &qr);
    for (int i = 1; i <= blng[n]; i++) {
      int p1 = lower_bound(X + L[i], X + R[i] + 1, ql) - X;
      int p2 = upper_bound(X + L[i], X + R[i] + 1, qr) - X - 1;
      if (p1 < L[i] || p1 > R[i] || p2 < L[i] || p2 > R[i] || p2 < p1) continue;
      if (ans == -1)
        ans = Set[make_pair(Q[i], make_pair(p1, p2))];
      else
        ans = Merge(ans, Set[make_pair(Q[i], make_pair(p1, p2))]);
    }
    res[qry] = ans;
  }
  printf("%d\n", cnt);
  for (int i = 0; i < opt.size(); i++)
    printf("%d %d\n", opt[i].first, opt[i].second);
  for (int i = 1; i <= q; i++) printf("%d ", res[i]);
  return 0;
}
