#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
pair<int, int> s[400];
bool smth[N];
int add[N];
int lastChange[N];
void upd(int v, int version, int value) {
  if (lastChange[v] != version) {
    lastChange[v] = version;
    add[v] = 0;
  }
  add[v] += value;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  if (n == 1) {
    cout << "0\n0\n";
    return 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> s[i].first >> s[i].second;
    smth[--s[i].first] = true;
    smth[--s[i].second] = true;
  }
  vector<int> toCheck;
  int cur = 0;
  for (int i = 0; i < n; i++) {
    if (a[cur] > a[i]) {
      cur = i;
    }
    if (smth[i]) {
      toCheck.push_back(cur);
      toCheck.push_back(i);
      cur = i + 1;
    }
  }
  if (cur != n) {
    toCheck.push_back(cur);
  }
  int ans = abs(a[0] - a[1]);
  int mn = 0;
  int mx = 1;
  if (a[0] > a[1]) {
    swap(mn, mx);
  }
  int version = 0;
  for (int i : toCheck) {
    version++;
    int x = a[i];
    for (int k = 0; k < m; k++) {
      if (s[k].first <= i && i <= s[k].second) {
        upd(s[k].first, version, -1);
        upd(s[k].second + 1, version, 1);
        x--;
      }
    }
    int sum = 0;
    for (int j = 0; j < n; j++) {
      if (lastChange[j] == version) {
        sum += add[j];
      }
      if (x < a[j] + sum && ans < a[j] + sum - x) {
        ans = a[j] + sum - x;
        mn = i;
        mx = j;
      }
    }
  }
  cerr << mn << ' ' << mx << endl;
  cout << ans << endl;
  vector<int> ansS;
  for (int i = 0; i < m; i++) {
    if (s[i].first <= mn && mn <= s[i].second) {
      ansS.push_back(i + 1);
    }
  }
  cout << ansS.size() << endl;
  for (int i : ansS) {
    cout << i << ' ';
  }
}
