#include <bits/stdc++.h>
static const int MaxSize = 1e5;
int tree[4 * MaxSize][2];
static void build(std::vector<int> &v, int vertex, int tl, int tr) {
  if (tl == tr)
    tree[vertex][0] = v[tl];
  else {
    int tm = (tl + tr) / 2;
    build(v, 2 * vertex + 1, tl, tm + 0);
    build(v, 2 * vertex + 2, tm + 1, tr);
    tree[vertex][0] =
        std::min(tree[2 * vertex + 1][0], tree[2 * vertex + 2][0]);
  }
}
static void update(int vertex, int tl, int tr, int l, int r, int x) {
  if (l > r) return;
  if (l == tl && tr == r)
    tree[vertex][1] += x;
  else {
    int tm = (tl + tr) / 2;
    update(2 * vertex + 1, tl, tm + 0, l, std::min(r, tm + 0), x);
    update(2 * vertex + 2, tm + 1, tr, std::max(l, tm + 1), r, x);
    tree[vertex][0] =
        std::min(tree[2 * vertex + 1][0] + tree[2 * vertex + 1][1],
                 tree[2 * vertex + 2][0] + tree[2 * vertex + 2][1]);
  }
}
static int get(int vertex, int tl, int tr, int l, int r, int x) {
  if (l == tl && tr == r) return tree[vertex][0] + tree[vertex][1];
  x += tree[vertex][1];
  int tm = (tl + tr) / 2;
  return std::min(
      x + get(2 * vertex + 1, tl, tm + 0, l, std::min(r, tm + 0), x),
      x + get(2 * vertex + 2, tm + 1, tr, std::max(l, tm + 1), r, x));
}
static void build(std::vector<int> &v, int n) { build(v, 0, 0, n - 1); }
static void update(int n, int l, int r, int x) { update(0, 0, n - 1, l, r, x); }
static int get(int n, int l, int r) { return get(0, 0, n - 1, l, r, 0); }
int main(int argc, const char *argv[]) {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> v(n), tree(4 * n);
  for (int i = 0; i < n; i++) std::cin >> v[i];
  std::vector<std::pair<int, int>> p(m);
  for (int i = 0; i < m; i++) {
    std::cin >> p[i].first >> p[i].second;
    p[i].first--;
    p[i].second--;
  }
  build(v, n);
  std::vector<bool> used(m);
  std::vector<int> t(4 * n), r;
  int result = 0;
  for (int i = 0; i < n; i++) {
    std::vector<int> intervals;
    for (int j = 0; j < m; j++) {
      if (p[j].first <= i && i <= p[j].second) {
        if (used[j]) {
          used[j] = false;
          update(n, p[j].first, p[j].second, 1);
        }
      } else {
        if (!used[j]) update(n, p[j].first, p[j].second, -1);
        intervals.push_back(j + 1);
        used[j] = true;
      }
    }
    int curr = v[i] - get(n, 0, n - 1);
    if (result < curr) {
      result = curr;
      std::swap(r, intervals);
    }
  }
  std::cout << result << std::endl;
  std::cout << r.size() << std::endl;
  if (r.size() > 0) {
    for (int number : r) std::cout << number << " ";
    std::cout << std::endl;
  }
  return 0;
}
