#include <bits/stdc++.h>
using namespace std;
const int N = 8e5 + 7;
int le[307], ri[307], n, m, in[N], val, is[N];
vector<int> st(N);
vector<int> lazy(N, 0);
void build(int x, int l, int r) {
  if (l == r) {
    st[x] = in[l];
  } else {
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    st[x] = min(st[x << 1], st[x << 1 | 1]);
  }
}
void pushUpdate(int x, int l, int r) {
  if (lazy[x] == 0) return;
  st[x] += lazy[x];
  lazy[x << 1] += lazy[x];
  lazy[x << 1 | 1] += lazy[x];
  lazy[x] = 0;
}
void update(int x, int l, int r, int i, int j) {
  pushUpdate(x, l, r);
  if (l > j || r < i || l > r) return;
  if (l >= i && r <= j) {
    st[x] += val;
    lazy[x << 1] += val;
    lazy[x << 1 | 1] += val;
    return;
  }
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, i, j);
  update(x << 1 | 1, mid + 1, r, i, j);
  st[x] = min(st[x << 1], st[x << 1 | 1]);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> in[i];
  for (int i = 0; i < m; ++i) {
    cin >> le[i] >> ri[i];
    le[i]--;
    ri[i]--;
  }
  build(1, 0, n - 1);
  memset(is, 0, sizeof(is));
  int ans = -1e9, index = -1;
  for (int i = 0; i < m; ++i) {
    val = -1;
    update(1, 0, n - 1, le[i], ri[i]);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (le[j] == i) {
        val = 1;
        update(1, 0, n - 1, le[j], ri[j]);
      }
    }
    pushUpdate(1, 0, n - 1);
    int num = in[i] - st[1];
    if (num > ans) {
      ans = num;
      index = i;
    }
    for (int j = 0; j < m; ++j) {
      if (ri[j] == i) {
        val = -1;
        update(1, 0, n - 1, le[j], ri[j]);
      }
    }
  }
  cout << ans << "\n";
  vector<int> arr;
  for (int i = 0; i < m; ++i) {
    if (le[i] > index || ri[i] < index) arr.push_back(i + 1);
  }
  cout << arr.size() << "\n";
  for (auto el : arr) {
    cout << el << " ";
  }
  cout << "\n";
}
