#include <bits/stdc++.h>
using namespace std;
int num[100010];
int l[100010], r[100010];
int tree[100010 << 2];
int lazy[100010 << 2];
vector<int> v[100010];
void build(int l, int r, int rt) {
  if (l == r) {
    tree[rt] = num[l];
    lazy[rt] = 0;
    return;
  }
  int m = l + r >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
void update(int L, int R, int l, int r, int rt, int w) {
  if (L <= l && r <= R) {
    tree[rt] += w;
    lazy[rt] += w;
    return;
  }
  if (lazy[rt]) {
    tree[rt << 1] += lazy[rt];
    tree[rt << 1 | 1] += lazy[rt];
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;
  }
  int m = l + r >> 1;
  if (L <= m) update(L, R, l, m, rt << 1, w);
  if (R > m) update(L, R, m + 1, r, rt << 1 | 1, w);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int x, int l, int r, int rt) {
  if (l == r) return tree[rt];
  int m = l + r >> 1;
  if (lazy[rt]) {
    tree[rt << 1] += lazy[rt];
    tree[rt << 1 | 1] += lazy[rt];
    lazy[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;
  }
  int ans = -0x3f3f3f3f;
  if (x <= m)
    ans = query(x, l, m, rt << 1);
  else
    ans = query(x, m + 1, r, rt << 1 | 1);
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> num[i];
  build(1, n, 1);
  for (int i = 1; i <= m; ++i) {
    cin >> l[i] >> r[i];
    v[l[i]].emplace_back(i);
    v[r[i] + 1].emplace_back(-i);
  }
  long long ans = -0x3f3f3f3f;
  int mark;
  for (int i = 1; i <= n; ++i) {
    int sz = v[i].size();
    for (int j = 0; j < sz; j++) {
      int t = v[i][j];
      if (t > 0)
        update(l[t], r[t], 1, n, 1, -1);
      else
        update(l[-t], r[-t], 1, n, 1, 1);
    }
    long long maxx = tree[1];
    long long now = query(i, 1, n, 1);
    if (maxx - now > ans) {
      ans = maxx - now;
      mark = i;
    }
  }
  cout << ans << endl;
  long long number = 0;
  for (int i = 1; i <= m; ++i) {
    if (l[i] <= mark && r[i] >= mark) {
      number++;
    }
  }
  cout << number << endl;
  for (int i = 1; i <= m; ++i) {
    if (l[i] <= mark && r[i] >= mark) {
      cout << i << " ";
    }
  }
  return 0;
}
