#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
long long a[maxn];
struct qujian {
  int l, r;
} q[maxn];
struct Ans {
  vector<int> v;
  long long dis;
} ans, tmp;
vector<int> vec[maxn];
long long minv[maxn * 4];
long long maxv[maxn * 4];
long long tag[maxn * 4];
void build(int o, int L, int R) {
  if (L == R) {
    minv[o] = maxv[o] = a[L];
    return;
  }
  int M = (L + R) / 2;
  int lch = o << 1, rch = lch | 1;
  build(lch, L, M);
  build(rch, M + 1, R);
  minv[o] = min(minv[lch], minv[rch]);
  maxv[o] = max(maxv[lch], maxv[rch]);
}
int querymin(int o, int L, int R, int ql, int qr) {
  int M = (L + R) / 2;
  int lch = o << 1, rch = lch | 1;
  if (ql <= L && R <= qr) return minv[o];
  if (tag[o]) {
    int z = tag[o];
    tag[lch] += z;
    minv[lch] += z;
    maxv[lch] += z;
    tag[rch] += z;
    minv[rch] += z;
    maxv[rch] += z;
    tag[o] = 0;
  }
  if (qr <= M) return querymin(lch, L, M, ql, qr);
  if (ql > M) return querymin(rch, M + 1, R, ql, qr);
  return min(querymin(lch, L, M, ql, qr), querymin(rch, M + 1, R, ql, qr));
}
int querymax(int o, int L, int R, int ql, int qr) {
  int M = (L + R) / 2;
  int lch = o << 1, rch = lch | 1;
  if (ql <= L && R <= qr) return maxv[o];
  if (tag[o]) {
    int z = tag[o];
    tag[lch] += z;
    minv[lch] += z;
    maxv[lch] += z;
    tag[rch] += z;
    minv[rch] += z;
    maxv[rch] += z;
    tag[o] = 0;
  }
  if (qr <= M) return querymax(lch, L, M, ql, qr);
  if (ql > M) return querymax(rch, M + 1, R, ql, qr);
  return max(querymax(lch, L, M, ql, qr), querymax(rch, M + 1, R, ql, qr));
}
void update(int o, int L, int R, int x, int y) {
  if (L == R) {
    minv[o] = maxv[o] = y;
    return;
  }
  int M = (L + R) / 2, lch = o << 1, rch = lch | 1;
  if (x <= M)
    update(lch, L, M, x, y);
  else
    update(rch, M + 1, R, x, y);
  minv[o] = min(minv[lch], minv[rch]);
  maxv[o] = max(maxv[lch], maxv[rch]);
}
void add(int o, int L, int R, int ql, int qr, int z) {
  int M = (L + R) / 2;
  int lch = o << 1, rch = lch | 1;
  if (ql <= L && R <= qr) {
    tag[o] += z;
    minv[o] += z;
    maxv[o] += z;
    return;
  }
  if (tag[o]) {
    int t = tag[o];
    tag[lch] += t;
    minv[lch] += t;
    maxv[lch] += t;
    tag[rch] += t;
    minv[rch] += t;
    maxv[rch] += t;
    tag[o] = 0;
  }
  if (qr <= M)
    add(lch, L, M, ql, qr, z);
  else if (ql > M)
    add(rch, M + 1, R, ql, qr, z);
  else {
    add(lch, L, M, ql, qr, z);
    add(rch, M + 1, R, ql, qr, z);
  }
  minv[o] = min(minv[lch], minv[rch]);
  maxv[o] = max(maxv[lch], maxv[rch]);
}
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    for (int i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &q[i].l, &q[i].r);
      for (int j = 1; j <= n; j++) {
        if (!(q[i].l <= j && j <= q[i].r)) {
          vec[j].push_back(i);
        }
      }
    }
    ans.dis = 0;
    ans.v.clear();
    for (int i = 1; i <= n; i++) {
      int sz = vec[i].size();
      tmp.v.clear();
      for (int j = 0; j < sz; j++) {
        int id = vec[i][j];
        int l = q[id].l;
        int r = q[id].r;
        tmp.v.push_back(id);
        add(1, 1, n, l, r, -1);
      }
      long long mx = querymax(1, 1, n, 1, n);
      long long mn = querymin(1, 1, n, 1, n);
      tmp.dis = mx - mn;
      if (tmp.dis > ans.dis) {
        ans = tmp;
      }
      tmp.v.clear();
      for (int j = 0; j < sz; j++) {
        int id = vec[i][j];
        int l = q[id].l;
        int r = q[id].r;
        add(1, 1, n, l, r, 1);
      }
    }
    printf("%lld\n", ans.dis);
    int sz = ans.v.size();
    printf("%d\n", sz);
    for (int i = 0; i < sz; i++) {
      printf("%d ", ans.v[i]);
    }
    puts("");
  }
}
