#include <bits/stdc++.h>
using namespace std;
int a[100005];
int t[400005];
int d[400005];
pair<int, int> p[305];
pair<int, int> cp[305];
int n;
void build(int l, int r, int i) {
  d[i] = 0;
  if (l == r)
    t[i] = a[l];
  else {
    int m = (l + r) / 2;
    int L = 2 * i;
    build(l, m, L);
    build(m + 1, r, L + 1);
    t[i] = (t[L] < t[L + 1] ? t[L] : t[L + 1]);
  }
}
void update(int l, int r, int p, int x, int y, int i) {
  if (l > y || r < x) return;
  if (l <= x && r >= y) {
    d[i] += p;
    t[i] += p;
    return;
  }
  int m = (x + y) / 2;
  int L = 2 * i;
  update(l, r, p, x, m, L);
  update(l, r, p, m + 1, y, L + 1);
  t[i] = (t[L] < t[L + 1] ? t[L] : t[L + 1]) + d[i];
}
bool comp(pair<int, int> x, pair<int, int> y) { return (x.second < y.second); }
int main() {
  ios::sync_with_stdio(false);
  int m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    cin >> p[i].first >> p[i].second;
    p[i].first--;
    p[i].second--;
    cp[i] = p[i];
  }
  sort(p, p + m);
  int v = 0, an = -1000000007;
  build(0, n - 1, 1);
  for (int j = m - 1, i = n - 1; i >= 0; i--) {
    if (an < a[i] - t[1]) {
      an = a[i] - t[1];
      v = i;
    }
    while (j >= 0 && p[j].first >= i) {
      update(p[j].first, p[j].second, -1, 0, n - 1, 1);
      j--;
    }
  }
  sort(p, p + m, comp);
  build(0, n - 1, 1);
  for (int j = 0, i = 0; i < n; i++) {
    if (an < a[i] - t[1]) {
      an = a[i] - t[1];
      v = i;
    }
    while (j < m && p[j].second <= i) {
      update(p[j].first, p[j].second, -1, 0, n - 1, 1);
      j++;
    }
  }
  cout << an << endl;
  int c = 0;
  for (int i = 0; i < m; i++) {
    if (v < p[i].first || v > p[i].second) c++;
  }
  cout << c << endl;
  for (int i = 0; i < m; i++) {
    if (v < cp[i].first || v > cp[i].second) cout << i + 1 << ' ';
  }
}
