#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int inf = 0x7fffffff;
const double eps = 1e-6;
const int maxn = (int)(2e5) + 7;
inline int read() {
  int f = 1, num = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) num = (num << 1) + (num << 3) + (ch ^ 48), ch = getchar();
  return num * f;
}
int n, m, now, num, a[350], t[350], L[350], R[350], vis[350], cnt[350],
    ans[350];
void check(int pos) {
  for (int i = 1; i <= m; i++) {
    if (L[i] <= pos && pos <= R[i]) continue;
    vis[i] = 1;
    cnt[L[i]]--;
    cnt[R[i] + 1]++;
  }
  int ma = a[pos], mi = (int)(1e6);
  for (int i = 1; i <= n; i++) {
    cnt[i] += cnt[i - 1];
    t[i] += cnt[i] + a[i];
    mi = min(t[i], mi);
  }
  for (int i = 1; i <= n; i++) cnt[i] = t[i] = 0;
  if (ma - mi > now) {
    now = ma - mi;
    num = 0;
    for (int i = 1; i <= m; i++) {
      ans[i] = vis[i];
      vis[i] = 0;
      if (ans[i]) num++;
    }
  } else
    for (int i = 1; i <= m; i++) vis[i] = 0;
}
int main() {
  n = read(), m = read();
  int ma = (int)(-1e6), mi = (int)(1e6);
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    ma = max(ma, a[i]);
    mi = min(mi, a[i]);
  }
  now = ma - mi;
  for (int i = 1; i <= m; i++) {
    L[i] = read();
    R[i] = read();
  }
  for (int i = 1; i <= n; i++) check(i);
  printf("%d\n%d\n", now, num);
  for (int i = 1; i <= m; i++)
    if (ans[i]) printf("%d ", i);
  return 0;
}
