#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, sum, anssum, ansmx;
int a[200010], e[200010], s[200010];
int mini[200010], mx[200010], ans[200010];
int l[200010], r[200010];
inline void prework() {
  scanf("%d%d", &n, &m);
  int mx = -1e6, mini = 1e6;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    mx = max(mx, a[i]);
    mini = min(mini, a[i]);
  }
  ansmx = mx - mini;
  cnt = 0;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l[i], &r[i]);
    e[++cnt] = l[i];
    e[++cnt] = r[i] + 1;
  }
  e[++cnt] = 1;
  e[++cnt] = n + 1;
  sort(e + 1, e + 1 + cnt);
  cnt = unique(e + 1, e + 1 + cnt) - e - 1;
}
inline bool in(int i, int j, int l, int r) {
  if (l <= i && j <= r)
    return true;
  else
    return false;
}
inline void mainwork() {
  for (int i = 1; i <= cnt; i++) {
    mini[i] = mx[i] = a[e[i]];
    for (int j = e[i] + 1; j < e[i + 1]; j++)
      mini[i] = min(a[j], mini[i]), mx[i] = max(a[j], mx[i]);
  }
  for (int i = 1; i <= cnt; i++)
    for (int j = 1; j <= cnt; j++)
      if (i != j && e[i] <= n && e[j] <= n) {
        sum = 0;
        for (int k = 1; k <= m; k++)
          if (in(e[i], e[i + 1] - 1, l[k], r[k]) &&
              !in(e[j], e[j + 1] - 1, l[k], r[k]))
            s[++sum] = k;
        if (mx[j] - mini[i] + sum > ansmx) {
          ansmx = mx[j] - mini[i] + sum;
          anssum = sum;
          for (int k = 1; k <= sum; k++) ans[k] = s[k];
        }
      }
}
inline void print() {
  printf("%d\n", ansmx);
  printf("%d\n", anssum);
  if (anssum == 0) puts("");
  for (int i = 1; i <= anssum; i++)
    printf("%d%c", ans[i], (i == anssum) ? '\n' : ' ');
}
int main() {
  prework();
  mainwork();
  print();
  return 0;
}
