#include <bits/stdc++.h>
using namespace std;
int segmented_tree_max[100001 * 17], segmented_tree_min[100001 * 17],
    lazy[100001 * 17];
int a[100001], n, q;
vector<pair<int, int> > apl;
vector<int> updator_apl[100001 + 1], updator_remove[100001 + 1];
void bulid(int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    segmented_tree_max[id] = a[l];
    segmented_tree_min[id] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  bulid(2 * id, l, mid);
  bulid(2 * id + 1, mid, r);
  segmented_tree_max[id] =
      max(segmented_tree_max[2 * id], segmented_tree_max[2 * id + 1]);
  segmented_tree_min[id] =
      min(segmented_tree_min[2 * id], segmented_tree_min[2 * id + 1]);
}
void lazy_update(int id, int l, int r, int x) {
  lazy[id] += x;
  segmented_tree_max[id] += x;
  segmented_tree_min[id] += x;
}
void shift(int id, int l, int r) {
  int mid = (l + r) / 2;
  lazy_update(2 * id, l, mid, lazy[id]);
  lazy_update(2 * id + 1, mid, r, lazy[id]);
  lazy[id] = 0;
}
void increase(int x, int y, int v, int id = 1, int l = 0, int r = n) {
  if ((x >= r) || (y <= l)) return;
  if ((x <= l) && (y >= r)) {
    lazy_update(id, l, r, v);
    return;
  }
  shift(id, l, r);
  int mid = (l + r) / 2;
  increase(x, y, v, 2 * id, l, mid);
  increase(x, y, v, 2 * id + 1, mid, r);
  segmented_tree_max[id] =
      max(segmented_tree_max[2 * id], segmented_tree_max[2 * id + 1]);
  segmented_tree_min[id] =
      min(segmented_tree_min[2 * id], segmented_tree_min[2 * id + 1]);
}
int ans_max(int x, int y, int id = 1, int l = 0, int r = n) {
  if ((x >= r) || (y <= l)) return INT_MIN;
  if ((x <= l) && (y >= r)) {
    return segmented_tree_max[id];
  }
  shift(id, l, r);
  int mid = (l + r) / 2;
  return (
      max(ans_max(x, y, 2 * id, l, mid), ans_max(x, y, 2 * id + 1, mid, r)));
}
int ans_min(int x, int y, int id = 1, int l = 0, int r = n) {
  if ((x >= r) || (y <= l)) return INT_MAX;
  if ((x <= l) && (y >= r)) {
    return segmented_tree_min[id];
  }
  int mid = (l + r) / 2;
  return (
      min(ans_min(x, y, 2 * id, l, mid), ans_min(x, y, 2 * id + 1, mid, r)));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < q; ++i) {
    pair<int, int> varr;
    cin >> varr.first >> varr.second;
    apl.push_back(varr);
    updator_apl[varr.first - 1].push_back(i);
    updator_remove[varr.second].push_back(i);
  }
  bulid();
  int maxx = 0;
  vector<int> ans;
  maxx = ans_max(0, n) - ans_min(0, n);
  multiset<int> temp;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < updator_apl[i].size(); ++j) {
      pair<int, int> w = apl[updator_apl[i][j]];
      increase(w.first - 1, w.second, -1);
      temp.insert(updator_apl[i][j] + 1);
    }
    for (int j = 0; j < updator_remove[i].size(); ++j) {
      pair<int, int> w = apl[updator_remove[i][j]];
      increase(w.first - 1, w.second, 1);
      temp.erase(updator_remove[i][j] + 1);
    }
    int pp = ans_max(0, n);
    pp -= ans_min(0, n);
    if (pp > maxx) {
      maxx = pp;
      ans.clear();
      for (auto x : temp) ans.push_back(x);
    }
  }
  cout << maxx << endl;
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
  return 0;
}
