#include <bits/stdc++.h>
using namespace std;
const int Q = 1 << 19;
vector<pair<int, int>> ad;
vector<int> va[Q], bel[Q], nxt[Q], pos[Q];
unordered_map<int, int> rem[Q];
int L[Q], R[Q];
int tot, p[Q];
void Init(int now, int l, int r) {
  if (l == r) {
    va[now].push_back(p[l]);
    rem[now][0] = p[l];
    return;
  }
  int mid = (l + r) >> 1;
  Init((now << 1), l, mid), Init((now << 1 | 1), mid + 1, r);
  int sl = mid - l + 1, sr = r - mid, pl = 0, pr = 0;
  pos[now].resize(r - l + 1);
  va[now].resize(r - l + 1), bel[now].resize(r - l + 1),
      nxt[now].resize(r - l + 1);
  for (int o = 0; o < r - l + 1; o++)
    if (pr == sr || (pl < sl && va[(now << 1)][pl] < va[(now << 1 | 1)][pr]))
      pos[now][o] = pl, va[now][o] = va[(now << 1)][pl++], bel[now][o] = 0;
    else
      pos[now][o] = pr, va[now][o] = va[(now << 1 | 1)][pr++], bel[now][o] = 1;
  if (!bel[now].back())
    nxt[now][r - l] = sr;
  else
    nxt[now][r - l] = sl;
  for (int i = r - l - 1; i >= 0; --i)
    if (bel[now][i] != bel[now][i + 1])
      nxt[now][i] = pos[now][i + 1];
    else
      nxt[now][i] = nxt[now][i + 1];
}
void Get(int now, int l, int r, int x, int y) {
  if (rem[now].count((((x) << 13) + (y)))) return;
  assert(l < r);
  int mid = (l + r) >> 1;
  int lx = pos[now][x], rx = nxt[now][x], ly = pos[now][y],
      ry = nxt[now][y] - 1;
  if (bel[now][x]) swap(lx, rx);
  if (bel[now][y]) swap(ly, ry);
  if (lx <= ly) Get((now << 1), l, mid, lx, ly);
  if (rx <= ry) Get((now << 1 | 1), mid + 1, r, rx, ry);
  if (lx > ly)
    rem[now][(((x) << 13) + (y))] = rem[(now << 1 | 1)][(((rx) << 13) + (ry))];
  else if (rx > ry)
    rem[now][(((x) << 13) + (y))] = rem[(now << 1)][(((lx) << 13) + (ly))];
  else
    rem[now][(((x) << 13) + (y))] = ++tot,
                            ad.push_back(make_pair(
                                rem[(now << 1)][(((lx) << 13) + (ly))],
                                rem[(now << 1 | 1)][(((rx) << 13) + (ry))]));
}
int main() {
  int n, qaq;
  scanf("%d%d", &n, &qaq);
  tot = n;
  for (int i = 1, x; i <= n; i++) scanf("%d", &x), p[x] = i;
  Init(1, 1, n);
  for (int i = 1; i <= qaq; i++)
    scanf("%d%d", &L[i], &R[i]), --L[i], --R[i], Get(1, 1, n, L[i], R[i]);
  printf("%d\n", tot);
  for (auto p : ad) printf("%d %d\n", p.first, p.second);
  for (int i = 1; i <= qaq; i++)
    printf("%d ", rem[1][(((L[i]) << 13) + (R[i]))]);
  return 0;
}
