#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 41;
const int mod = 1e9 + 7;
const long long INF = 1e18;
const int inf = 2e9;
int a[N], l[N], r[N];
vector<int> add[N], del[N];
int mn[N * 4];
void build(int l = 0, int r = N, int v = 0) {
  if (r - l == 1) {
    mn[v] = a[l];
    return;
  }
  int m = (l + r) / 2;
  build(l, m, v + v + 1), build(m, r, v + v + 2);
  mn[v] = min(mn[v + v + 1], mn[v + v + 2]);
}
int p[N * 4];
void push(int v) {
  mn[v] += p[v];
  p[v + v + 1] += p[v];
  p[v + v + 2] += p[v];
  p[v] = 0;
}
void upd(int L, int R, int val, int l = 0, int r = N, int v = 0) {
  push(v);
  if (L <= l && r <= R) {
    p[v] += val;
    push(v);
    return;
  }
  if (r <= L || R <= l) {
    return;
  }
  int m = (l + r) / 2;
  upd(L, R, val, l, m, v + v + 1), upd(L, R, val, m, r, v + v + 2);
  mn[v] = min(mn[v + v + 1], mn[v + v + 2]);
}
int get(int L, int R, int l = 0, int r = N, int v = 0) {
  push(v);
  if (L <= l && r <= R) {
    return mn[v];
  }
  if (r <= L || R <= l) {
    return inf;
  }
  int m = (l + r) / 2;
  return min(get(L, R, l, m, v + v + 1), get(L, R, m, r, v + v + 2));
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  int n, m, ans = 0, ansi = -1, ansc = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  ans = *max_element(a + 1, a + 1 + n) - *min_element(a + 1, a + 1 + n);
  build();
  for (int i = 1; i <= m; ++i) {
    cin >> l[i] >> r[i];
    add[l[i]].push_back(r[i]);
    del[r[i]].push_back(l[i]);
    upd(l[i], r[i] + 1, -1);
  }
  int cnt = m;
  for (int i = 1; i <= n; ++i) {
    for (int j : add[i]) {
      --cnt;
      upd(i, j + 1, +1);
    }
    int cur = a[i] - get(1, n + 1);
    if (ans < cur) {
      ans = cur;
      ansi = i;
      ansc = cnt;
    }
    for (int j : del[i]) {
      ++cnt;
      upd(j, i + 1, -1);
    }
  }
  if (ansi == -1) {
    cout << ans << "\n0";
    return 0;
  }
  cout << ans << "\n" << ansc << "\n";
  for (int i = 1; i <= m; ++i) {
    if (ansi < l[i] || ansi > r[i]) cout << i << " ";
  }
}
