#include <bits/stdc++.h>
using namespace std;
long long int arr[100010];
struct node {
  long long int ma;
  long long int mi;
  long long int lazy;
};
node st[400010];
long long int n, m;
vector<long long int> start[100010];
std::vector<long long int> endr[100010];
void build(long long int ss, long long int se, long long int si) {
  if (ss > se) {
    return;
  }
  if (ss == se) {
    st[si].mi = st[si].ma = arr[ss];
    return;
  }
  long long int mid = (ss + se) / 2;
  build(ss, mid, 2 * si + 1);
  build(mid + 1, se, 2 * si + 2);
  st[si].mi = min(st[2 * si + 1].mi, st[2 * si + 2].mi);
  st[si].ma = max(st[2 * si + 1].ma, st[2 * si + 2].ma);
}
void update(long long int ss, long long int se, long long int qs,
            long long int qe, long long int value, long long int si) {
  if (st[si].lazy) {
    st[si].mi += st[si].lazy;
    st[si].ma += st[si].lazy;
    if (ss != se) {
      st[2 * si + 1].lazy += st[si].lazy;
      st[2 * si + 2].lazy += st[si].lazy;
    }
    st[si].lazy = 0;
  }
  if (ss > se || ss > qe || se < qs) {
    return;
  }
  if (ss >= qs && se <= qe) {
    st[si].mi += value;
    st[si].ma += value;
    if (ss != se) {
      st[2 * si + 1].lazy += value;
      st[2 * si + 2].lazy += value;
    }
    return;
  }
  long long int mid = (ss + se) / 2;
  update(ss, mid, qs, qe, value, 2 * si + 1);
  update(mid + 1, se, qs, qe, value, 2 * si + 2);
  st[si].mi = min(st[2 * si + 1].mi, st[2 * si + 2].mi);
  st[si].ma = max(st[2 * si + 1].ma, st[2 * si + 2].ma);
}
node query(long long int ss, long long int se, long long int qs,
           long long int qe, long long int si) {
  if (ss > se || ss > qe || se < qs) {
    node tem;
    tem.mi = LLONG_MAX;
    tem.ma = -LLONG_MAX;
    return tem;
  }
  if (ss >= qs && se <= qe) {
    return st[si];
  }
  long long int mid = (ss + se) / 2;
  node a = query(ss, mid, qs, qe, 2 * si + 1);
  node b = query(mid + 1, se, qs, qe, 2 * si + 2);
  node ans;
  ans.ma = max(a.ma, b.ma);
  ans.mi = min(a.mi, b.mi);
  return ans;
}
void printTree() {
  long long int x = (long long int)(ceil(log2(n)));
  long long int maz = 2 * (long long int)pow(2, x) - 1;
  for (long long int i = 0; i < maz; i++) {
    cout << "Index " << i << " : \n";
    cout << "Max is :" << st[i].ma << "\n";
    cout << "Min is : " << st[i].mi << "\n";
    cout << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
  cin >> n >> m;
  for (long long int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  long long int l[m], r[m];
  build(0, n - 1, 0);
  for (long long int i = 0; i < m; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
    start[l[i]].push_back(r[i]);
    endr[r[i]].push_back(l[i]);
    update(0, n - 1, l[i], r[i], -1, 0);
  }
  long long int ans = 0;
  long long int best = -1;
  for (long long int i = 0; i < n; i++) {
    for (auto j : start[i]) {
      update(0, n - 1, i, j, 1, 0);
    }
    node xx = query(0, n - 1, 0, n - 1, 0);
    if ((xx.ma - xx.mi) > ans) {
      best = i;
      ans = (xx.ma - xx.mi);
    }
    for (auto j : endr[i]) {
      update(0, n - 1, j, i, -1, 0);
    }
  }
  cout << ans << endl;
  std::vector<long long int> range;
  for (long long int i = 0; i < m; i++) {
    if (!(best >= l[i] && best <= r[i])) {
      range.push_back(i + 1);
    }
  }
  cout << range.size() << "\n";
  for (auto i : range) {
    cout << i << " ";
  }
  cout << "\n";
  return 0;
}
