#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
struct node {
  ll mi;
  ll mx;
} tree[maxn * 4], back[maxn * 4];
int a[maxn];
int add[maxn * 4];
int lef[maxn];
int rig[maxn];
void pushup(int now) {
  tree[now].mi = min(tree[now * 2].mi, tree[now * 2 + 1].mi);
  tree[now].mx = max(tree[now * 2].mx, tree[now * 2 + 1].mx);
}
void build(int l, int r, int now) {
  if (l == r) {
    tree[now].mi = tree[now].mx = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, now * 2);
  build(mid + 1, r, now * 2 + 1);
  pushup(now);
}
void pushdown(int now) {
  if (add[now]) {
    add[now * 2] += add[now];
    add[now * 2 + 1] += add[now];
    tree[now * 2].mi += add[now];
    tree[now * 2].mx += add[now];
    tree[now * 2 + 1].mi += add[now];
    tree[now * 2 + 1].mx += add[now];
    add[now] = 0;
  }
}
void update(int L, int R, int l, int r, int now, int val) {
  if (L <= l && R >= r) {
    tree[now].mi += val;
    tree[now].mx += val;
    add[now] += val;
    return;
  }
  int mid = (l + r) / 2;
  pushdown(now);
  if (L <= mid) {
    update(L, R, l, mid, now * 2, val);
  }
  if (R > mid) {
    update(L, R, mid + 1, r, now * 2 + 1, val);
  }
  pushup(now);
}
int main() {
  std::ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  build(1, n, 1);
  vector<int> seg;
  for (int i = 1; i <= m; ++i) {
    cin >> lef[i] >> rig[i];
    seg.push_back(lef[i]);
    seg.push_back(rig[i]);
  }
  sort(seg.begin(), seg.end());
  seg.erase(unique(seg.begin(), seg.end()), seg.end());
  int ans = tree[1].mx - tree[1].mi;
  vector<int> choose;
  memcpy(back, tree, sizeof(back));
  for (int p : seg) {
    memcpy(tree, back, sizeof(back));
    memset(add, 0, sizeof(add));
    vector<int> tmp;
    for (int i = 1; i <= m; ++i) {
      if (lef[i] <= p && rig[i] >= p) {
        update(lef[i], rig[i], 1, n, 1, -1);
        tmp.push_back(i);
      }
    }
    if (tree[1].mx - tree[1].mi > ans) {
      ans = tree[1].mx - tree[1].mi;
      choose = tmp;
    }
  }
  cout << ans << endl;
  cout << choose.size() << endl;
  for (int v : choose) {
    cout << v << " ";
  }
  cout << endl;
  return 0;
}
