#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 10;
int n, m;
int a[N], l[N], r[N], vis[N];
int d[N];
int getAns(int pos) {
  for (int i = 1; i <= n + 1; i++) d[i] = 0;
  for (int i = 1; i <= m; i++) {
    if (r[i] < pos || l[i] > pos) {
      d[l[i]] += -1;
      d[r[i] + 1] += 1;
    }
  }
  for (int i = 1; i <= n; i++) d[i] += d[i - 1];
  int mn = N;
  for (int i = 1; i <= n; i++) {
    mn = min(d[i] + a[i], mn);
  }
  return a[pos] - mn;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &l[i], &r[i]);
    vis[l[i]] = 1, vis[r[i]] = 1;
  }
  int ans = -1, bst = 0;
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 1) {
      int tmp = getAns(i);
      if (tmp >= ans) {
        ans = tmp;
        bst = i;
      }
    } else {
      int j = i;
      int mx = -N, pos = j;
      while (j <= n && vis[j] == 0) {
        if (a[j] >= mx) {
          mx = a[j];
          pos = j;
        }
        j++;
      }
      i = j - 1;
      int tmp = getAns(pos);
      if (tmp >= ans) {
        ans = tmp;
        bst = i;
      }
    }
  }
  cout << ans << endl;
  vector<int> res;
  res.clear();
  for (int i = 1; i <= m; i++) {
    if (r[i] < bst || l[i] > bst) res.push_back(i);
  }
  printf("%d\n", res.size());
  for (int i = 0; i < res.size(); i++) printf("%d ", res[i]);
}
