#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 10;
int a[MAX_N];
vector<pair<int, int>> scanCuts[2][MAX_N];
pair<int, int> cuts[MAX_N];
int tree[2 * MAX_N], d[2 * MAX_N];
void push(int i) {
  d[2 * i + 1] += d[i];
  d[2 * i + 2] += d[i];
  tree[2 * i + 1] += d[i];
  tree[2 * i + 2] += d[i];
  d[i] = 0;
}
void pull(int i) {
  tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
  tree[i] += d[i];
}
void build(int i, int l, int r) {
  if (r - l == 1) {
    tree[i] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(2 * i + 1, l, mid);
  build(2 * i + 2, mid, r);
  pull(i);
}
void add(int l, int r, int x, int i, int cl, int cr) {
  if (r <= cl || cr <= l) return;
  if (l <= cl && cr <= r) {
    tree[i] += x;
    d[i] += x;
    return;
  }
  int mid = (cl + cr) / 2;
  add(l, r, x, 2 * i + 1, cl, mid);
  add(l, r, x, 2 * i + 2, mid, cr);
  pull(i);
}
int get(int l, int r, int i, int cl, int cr) {
  if (r <= cl || cr <= l) return +1e9;
  if (l <= cl && cr <= r) return tree[i];
  int mid = (cl + cr) / 2;
  push(i);
  return min(get(l, r, 2 * i + 1, cl, mid), get(l, r, 2 * i + 2, mid, cr));
}
void print(int i, int cl, int cr) {
  cout << i << " (" << cl << "; " << cr << ") -> " << tree[i] << " " << d[i]
       << "\n";
  if (cr - cl == 1) return;
  int mid = (cl + cr) / 2;
  print(2 * i + 1, cl, mid);
  print(2 * i + 2, mid, cr);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i];
  build(0, 0, n);
  set<int> bestAns;
  set<int> currAns;
  for (int i = 0; i < q; ++i) {
    cin >> cuts[i].first >> cuts[i].second;
    --cuts[i].first;
    currAns.insert(i);
    add(cuts[i].first, cuts[i].second, -1, 0, 0, n);
    scanCuts[0][cuts[i].first].push_back({cuts[i].second, i});
    scanCuts[1][cuts[i].second].push_back({cuts[i].first, i});
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (auto u : scanCuts[0][i]) {
      add(i, u.first, 1, 0, 0, n);
      currAns.erase(u.second);
    }
    for (auto u : scanCuts[1][i]) {
      add(u.first, i, -1, 0, 0, n);
      currAns.insert(u.second);
    }
    int lans = get(i, i + 1, 0, 0, n) - get(0, n, 0, 0, n);
    if (lans > ans) {
      ans = lans;
      bestAns = currAns;
    }
  }
  cout << ans << "\n";
  cout << bestAns.size() << "\n";
  for (int u : bestAns) cout << u + 1 << " ";
  return 0;
}
