#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 12, M = 1 << 16, B = 1 << 8, K = 1 << 22;
int n, m, tot, a[N], c[K], d[K], pos[N], ans[M];
inline int merge(int x, int y) {
  if (!x || !y) return x + y;
  return c[tot] = x, d[tot] = y, ++tot;
}
struct seg {
  vector<int> val;
  vector<vector<int> > id;
  inline void init(int x) {
    val.resize(x), id.resize(x);
    for (int i = 0; i <= x - 1; i++) id[i].resize(x - i);
  }
  seg() {}
  seg(int x) { init(1), val[0] = pos[x], id[0][0] = pos[x] + 1; }
  int ask(int l, int r) const {
    if (r < val.front() || l > val.back()) return 0;
    l = lower_bound(val.begin(), val.end(), l) - val.begin();
    r = upper_bound(val.begin(), val.end(), r) - val.begin() - 1;
    return l > r ? 0 : id[l][r - l];
  }
} t[N / B + 5];
seg update(const seg& x, const seg& y) {
  seg cur;
  cur.init(x.val.size() + y.val.size());
  merge(x.val.begin(), x.val.end(), y.val.begin(), y.val.end(),
        cur.val.begin());
  for (int i = 0; i <= cur.val.size() - 1; i++)
    for (int j = i; j <= cur.val.size() - 1; j++)
      cur.id[i][j - i] =
          merge(x.ask(cur.val[i], cur.val[j]), y.ask(cur.val[i], cur.val[j]));
  return cur;
}
inline void input() {
  scanf("%d%d", &n, &m), tot = n--;
  for (int i = 0; i <= n; i++) scanf("%d", a + i), a[i]--;
}
seg solve(int L, int R) {
  if (L == R) return (L);
  int mid = L + R >> 1;
  return update(solve(L, mid), solve(mid + 1, R));
}
inline void init() {
  for (int i = 0; i <= n; i++) pos[a[i]] = i;
  for (int i = 0; i <= n / B; i++) t[i] = solve(i * B, min(n, i * B + B - 1));
}
inline void work() {
  int l, r;
  for (int i = 0; i <= m - 1; i++) {
    scanf("%d%d", &l, &r), l--, r--;
    for (int j = 0; j <= n / B; j++) ans[i] = merge(ans[i], t[j].ask(l, r));
  }
  cout << tot << '\n';
  for (int i = n + 1; i <= tot - 1; i++) cout << c[i] << ' ' << d[i] << '\n';
  for (int i = 0; i <= m - 1; i++) cout << ans[i] << ' ';
}
int main() {
  input();
  init();
  work();
  return 0;
}
