#include <bits/stdc++.h>
using namespace std;
std::vector<int> a;
std::vector<pair<int, int> > leftbegin;
std::vector<pair<int, int> > rightend;
std::vector<pair<int, int> > ranges;
std::map<pair<int, int>, int> pairmap;
std::vector<int> lazy(400005);
vector<int> segtree(400005);
void build(int node, int l, int r) {
  int mid = (l + r) / 2;
  if (l == r) {
    segtree[node] = a[l];
    return;
  }
  build(2 * node + 1, l, mid);
  build(2 * node + 2, mid + 1, r);
  segtree[node] = min(segtree[2 * node + 1], segtree[2 * node + 2]);
}
void updateRange(int node, int start, int end, int l, int r, int val) {
  if (lazy[node] != 0) {
    segtree[node] += lazy[node];
    if (start != end) {
      lazy[node * 2 + 1] += lazy[node];
      lazy[node * 2 + 2] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (start > end or start > r or end < l) return;
  if (start >= l and end <= r) {
    segtree[node] += val;
    if (start != end) {
      lazy[node * 2 + 1] += val;
      lazy[node * 2 + 2] += val;
    }
    return;
  }
  int mid = (start + end) / 2;
  updateRange(node * 2 + 1, start, mid, l, r, val);
  updateRange(node * 2 + 2, mid + 1, end, l, r, val);
  segtree[node] = min(segtree[node * 2 + 1], segtree[node * 2 + 2]);
}
int queryRange(int node, int start, int end, int l, int r) {
  if (start > end or start > r or end < l) return INT_MAX;
  if (lazy[node] != 0) {
    segtree[node] += lazy[node];
    if (start != end) {
      lazy[node * 2 + 1] += lazy[node];
      lazy[node * 2 + 2] += lazy[node];
    }
    lazy[node] = 0;
  }
  if (start >= l and end <= r) return segtree[node];
  int mid = (start + end) / 2;
  int p1 = queryRange(node * 2 + 1, start, mid, l, r);
  int p2 = queryRange(node * 2 + 2, mid + 1, end, l, r);
  return min(p1, p2);
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  build(0, 0, n - 1);
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    leftbegin.push_back({l, i});
    rightend.push_back({r, i});
    ranges.push_back({l, r});
    updateRange(0, 0, n - 1, l, r, -1);
  }
  sort(leftbegin.begin(), leftbegin.end());
  sort(rightend.begin(), rightend.end());
  int ctr1 = 0;
  int ctr2 = 0;
  int ans = -1;
  std::vector<int> indices(m, 1);
  std::vector<int> ansindices;
  for (int i = 0; i < n; i++) {
    while (ctr1 < m && leftbegin[ctr1].first <= i) {
      updateRange(0, 0, n - 1, ranges[leftbegin[ctr1].second].first,
                  ranges[leftbegin[ctr1].second].second, 1);
      indices[leftbegin[ctr1].second] = 0;
      ctr1++;
    }
    while (ctr2 < m && rightend[ctr2].first < i) {
      updateRange(0, 0, n - 1, ranges[rightend[ctr2].second].first,
                  ranges[rightend[ctr2].second].second, -1);
      indices[rightend[ctr2].second] = 1;
      ctr2++;
    }
    for (int i = 0; i < m; ++i) {
    }
    if (ans < a[i] - queryRange(0, 0, n - 1, 0, n - 1)) {
      ans = a[i] - queryRange(0, 0, n - 1, 0, n - 1);
      ansindices = indices;
    }
  }
  cout << ans << endl;
  int count = 0;
  for (int i = 0; i < m; ++i) {
    count += ansindices[i];
  }
  cout << count << endl;
  for (int i = 0; i < m; ++i) {
    if (ansindices[i]) cout << i + 1 << ' ';
  }
}
