#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> inv;
int cnt;
vector<int> u, v;
struct Tree {
  int lo, hi;
  Tree *bot, *top;
  vector<int> numdwn;
  unordered_map<long long, int> mp;
  Tree(int *l, int *r, int x, int y) {
    lo = x, hi = y;
    if (lo == hi || l >= r) return;
    int mid = (lo + hi) / 2, cntdwn = 0;
    numdwn.reserve(r - l);
    for (int *p = l; p != r; ++p) {
      if (*p <= mid) ++cntdwn;
      numdwn.push_back(cntdwn);
    }
    int *divider = stable_partition(l, r, [mid](int v) { return v <= mid; });
    bot = new Tree(l, divider, lo, mid);
    top = new Tree(divider, r, mid + 1, hi);
  }
  int idof(int l, int r) {
    if (l > r) return -1;
    if (lo == hi) return inv[lo];
    long long code = ((long long)l) * n + r;
    if (mp.count(code)) return mp[code];
    int numbl = 0;
    if (l > 0) numbl = numdwn[l - 1];
    int numbr = numdwn[r], numb = numbr - numbl;
    int botid = bot->idof(numbl, numbr - 1);
    int topid = top->idof(l - numbl, r - numbr);
    int ans = -1;
    if (botid == -1)
      ans = topid;
    else if (topid == -1)
      ans = botid;
    else {
      ans = cnt++;
      u.push_back(botid);
      v.push_back(topid);
    }
    mp[code] = ans;
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) {
    cin >> a[i];
    --a[i];
  }
  inv.resize(n);
  for (int i = 0; i < (n); ++i) inv[a[i]] = i;
  auto acopy = a;
  cnt = n;
  Tree tree(&acopy[0], &acopy[0] + n, 0, n - 1);
  vector<int> lq(q), rq(q);
  for (int i = 0; i < (q); ++i) {
    cin >> lq[i] >> rq[i];
    --lq[i];
    --rq[i];
  }
  vector<int> ks(q);
  for (int i = 0; i < (q); ++i) {
    ks[i] = tree.idof(lq[i], rq[i]);
  }
  cout << cnt << "\n";
  for (int i = 0; i < ((int)(u).size()); ++i) {
    cout << u[i] + 1 << " " << v[i] + 1 << "\n";
  }
  for (int i = 0; i < (q); ++i) cout << ks[i] + 1 << " ";
  cout << "\n";
}
