#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int a[maxn];
pair<int, int> p[maxn], t[maxn << 2];
int lazy[maxn << 2];
vector<int> st[maxn], ed[maxn];
void build(int node, int b, int e) {
  if (b == e) {
    t[node] = make_pair(a[b], a[b]);
    return;
  }
  int mid = (b + e) >> 1;
  build(2 * node, b, mid);
  build(2 * node + 1, mid + 1, e);
  t[node] = make_pair(max(t[2 * node].first, t[2 * node + 1].first),
                      min(t[2 * node].second, t[2 * node + 1].second));
}
void push_down(int node, int b, int e) {
  if (lazy[node] != 0) {
    t[node].first += lazy[node];
    t[node].second += lazy[node];
    if (b != e) {
      lazy[2 * node] += lazy[node];
      lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
  }
}
void upd(int node, int b, int e, int i, int j, int val) {
  push_down(node, b, e);
  if (i > e || j < b) return;
  if (b >= i && j >= e) {
    lazy[node] += val;
    push_down(node, b, e);
    return;
  }
  int mid = (b + e) >> 1;
  upd(2 * node, b, mid, i, j, val);
  upd(2 * node + 1, mid + 1, e, i, j, val);
  t[node] = make_pair(max(t[2 * node].first, t[2 * node + 1].first),
                      min(t[2 * node].second, t[2 * node + 1].second));
}
pair<int, int> query(int node, int b, int e, int i, int j) {
  push_down(node, b, e);
  if (i > e || j < b) return make_pair(-1e8, 1e8);
  if (b >= i && j >= e) return t[node];
  int mid = (b + e) >> 1;
  pair<int, int> p1 = query(2 * node, b, mid, i, j);
  pair<int, int> p2 = query(2 * node + 1, mid + 1, e, i, j);
  pair<int, int> ret;
  ret.first = max(p1.first, p2.first);
  ret.second = min(p1.second, p2.second);
  return ret;
}
int main(int argc, char const *argv[]) {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d %d", &p[i].first, &p[i].second);
    st[p[i].first].push_back(i);
    ed[p[i].second].push_back(i);
  }
  if (n == 1) {
    printf("0\n0\n");
    return 0;
  }
  build(1, 1, n);
  int ans = -1e8, idx = -1;
  for (int i = 1; i <= n; ++i) {
    for (auto j : st[i]) upd(1, 1, n, p[j].first, p[j].second, -1);
    pair<int, int> ret = query(1, 1, n, 1, n);
    if (ret.first - ret.second > ans) {
      ans = ret.first - ret.second;
      idx = i;
    }
    for (auto j : ed[i]) upd(1, 1, n, p[j].first, p[j].second, 1);
  }
  printf("%d\n", ans);
  vector<int> v;
  for (int i = 1; i <= m; ++i) {
    if (p[i].first <= idx && p[i].second >= idx) {
      v.push_back(i);
    }
  }
  printf("%d\n", (int)v.size());
  for (auto i : v) printf("%d ", i);
  return 0;
}
