#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 5e4 + 10;
const int maxint = 0x3f3f3f3f;
const long long maxlonglong = 0x7f7f7f7f;
const int st = (1 << 20) - 1;
const int mod = 1e9 + 7;
const double eps = log2(1.01);
const int vec[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
struct node {
  int x, y;
} p[maxn];
int a[maxn], f[maxn << 2], f1[maxn << 2], tag[maxn << 2], b[maxn], ans[maxn],
    num[maxn];
void build(int p, int l, int r) {
  tag[p] = 0;
  if (l == r) {
    f1[p] = f[p] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  f[p] = max(f[p << 1], f[p << 1 | 1]);
  f1[p] = min(f1[p << 1], f1[p << 1 | 1]);
}
inline void push_down(int p) {
  f[p << 1] += tag[p];
  f[p << 1 | 1] += tag[p];
  f1[p << 1] += tag[p];
  f1[p << 1 | 1] += tag[p];
  tag[p << 1] += tag[p];
  tag[p << 1 | 1] += tag[p];
  tag[p] = 0;
}
inline void update(int nl, int nr, int l, int r, int p, int k) {
  if (nl <= l && r <= nr) {
    f[p] += k;
    f1[p] += k;
    tag[p] += k;
    return;
  }
  push_down(p);
  int mid = (l + r) >> 1;
  if (nl <= mid) update(nl, nr, l, mid, p << 1, k);
  if (nr > mid) update(nl, nr, mid + 1, r, p << 1 | 1, k);
  f[p] = max(f[p << 1], f[p << 1 | 1]);
  f1[p] = min(f1[p << 1], f1[p << 1 | 1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> p[i].x >> p[i].y;
  }
  build(1, 1, n);
  int pos = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (i >= p[j].x && i <= p[j].y) {
        if (!b[j]) update(p[j].x, p[j].y, 1, n, 1, -1), b[j] = 1;
        num[i]++;
      } else if (b[j]) {
        update(p[j].x, p[j].y, 1, n, 1, 1);
        b[j] = 0;
      }
    }
    ans[i] = f[1] - f1[1];
    if (ans[i] > ans[pos]) pos = i;
  }
  cout << ans[pos] << endl;
  cout << num[pos] << endl;
  for (int i = 1; i <= m; i++) {
    if (pos >= p[i].x && pos <= p[i].y) cout << i << ' ';
  }
  return 0;
}
