#include <bits/stdc++.h>
using namespace std;
int arr3[200010] = {0};
int arr[200010] = {0};
int arr1[200010] = {0};
int tree[500010] = {0};
int lazy[500010] = {0};
void build_tree(int node, int a, int b) {
  if (a > b) return;
  if (a == b) {
    tree[node] = arr[a];
    return;
  }
  build_tree(node * 2, a, (a + b) / 2);
  build_tree(node * 2 + 1, 1 + (a + b) / 2, b);
  tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
void update_tree(int node, int a, int b, int i, int j, int value) {
  if (lazy[node] != 0) {
    tree[node] += lazy[node];
    if (a != b) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (a > b || a > j || b < i) return;
  if (a >= i && b <= j) {
    tree[node] += value;
    if (a != b) {
      lazy[node * 2] += value;
      lazy[node * 2 + 1] += value;
    }
    return;
  }
  update_tree(node * 2, a, (a + b) / 2, i, j, value);
  update_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);
  tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int query_tree(int node, int a, int b, int i, int j) {
  if (a > b || a > j || b < i) return -10000000;
  if (lazy[node] != 0) {
    tree[node] += lazy[node];
    if (a != b) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (a >= i && b <= j) return tree[node];
  int q1 = query_tree(node * 2, a, (a + b) / 2, i, j);
  int q2 = query_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j);
  int res = max(q1, q2);
  return res;
}
struct segg {
  int pos, type, id;
  segg() {
    pos = -1;
    type = -1;
    id = -1;
  }
  segg(int a, int b, int c) {
    pos = a;
    type = b;
    id = c;
  }
  bool operator<(const segg &other) const {
    if (pos != other.pos) return pos < other.pos;
    if (type != other.type) return type < other.type;
    return id < other.id;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    arr1[i] = arr[i];
  }
  build_tree(1, 0, n - 1);
  set<segg> seg;
  vector<pair<int, int>> seg1;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    seg1.push_back(make_pair(l, r));
    seg.insert(segg(l - 1, 0, i));
    seg.insert(segg(r - 1, 1, i));
  }
  int ans = 0;
  set<int> temp;
  set<int> take;
  int infis = 0;
  for (int i = 0; i < n; i++) {
    while (!seg.empty()) {
      auto it = seg.begin();
      if (it->pos != i) break;
      if (it->type == 1) break;
      update_tree(1, 0, n - 1, seg1[it->id].first - 1, seg1[it->id].second - 1,
                  -1);
      take.insert(it->id);
      infis--;
      seg.erase(it);
    }
    int maxis = query_tree(1, 0, n - 1, 0, n - 1);
    if (ans < (maxis - infis - arr1[i])) {
      ans = maxis - infis - arr1[i];
      temp = take;
    }
    while (!seg.empty()) {
      auto it = seg.begin();
      if (it->pos != i) break;
      if (it->type == 0) break;
      update_tree(1, 0, n - 1, seg1[it->id].first - 1, seg1[it->id].second - 1,
                  +1);
      take.erase(it->id);
      infis++;
      seg.erase(it);
    }
  }
  cout << ans << '\n';
  cout << temp.size() << '\n';
  for (auto i : temp) {
    cout << i + 1 << ' ';
  }
  return 0;
}
