#include <bits/stdc++.h>
using namespace std;
void file() {}
void fast() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int N = 1e5 + 5;
int tree1[4 * N];
int tree2[4 * N];
int lazy[4 * N];
int arr[N];
void build(int node, int l, int r) {
  if (l == r) {
    tree1[node] = tree2[node] = arr[l];
    return;
  }
  int mid = (l + r) / 2;
  build(node * 2, l, mid);
  build(node * 2 + 1, mid + 1, r);
  tree1[node] = max(tree1[node * 2], tree1[node * 2 + 1]);
  tree2[node] = min(tree2[node * 2], tree2[node * 2 + 1]);
}
void propagate(int node, int l, int r) {
  tree1[node] += lazy[node];
  tree2[node] += lazy[node];
  if (l != r) {
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
  }
  lazy[node] = 0;
}
void update(int node, int l, int r, int s, int e, int val) {
  propagate(node, l, r);
  if (s > r || e < l) return;
  if (s <= l && r <= e) {
    tree1[node] += val;
    tree2[node] += val;
    if (l != r) {
      lazy[node * 2] += val;
      lazy[node * 2 + 1] += val;
    }
    return;
  }
  int mid = (l + r) / 2;
  update(node * 2, l, mid, s, e, val);
  update(node * 2 + 1, mid + 1, r, s, e, val);
  tree1[node] = max(tree1[node * 2], tree1[node * 2 + 1]);
  tree2[node] = min(tree2[node * 2], tree2[node * 2 + 1]);
}
int query1(int node, int l, int r, int s, int e) {
  propagate(node, l, r);
  if (r < s || l > e) return -1e8;
  if (s <= l && r <= e) return tree1[node];
  int mid = (l + r) / 2;
  return max(query1(node * 2, l, mid, s, e),
             query1(node * 2, mid + 1, r, s, e));
}
int query2(int node, int l, int r, int s, int e) {
  propagate(node, l, r);
  if (r < s || l > e) return 1e8;
  if (s <= l && r <= e) return tree2[node];
  int mid = (l + r) / 2;
  return min(query2(node * 2, l, mid, s, e),
             query2(node * 2, mid + 1, r, s, e));
}
int s[305][2];
vector<int> add[100005], rem[100005], v[1000005];
int main() {
  file();
  fast();
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  build(1, 1, n);
  int mx = query1(1, 1, n, 1, n) - query2(1, 1, n, 1, n), z = 0;
  for (int j = 1; j <= m; j++) {
    cin >> s[j][0] >> s[j][1];
    add[s[j][0]].push_back(j);
    rem[s[j][1] + 1].push_back(j);
    for (int i = 1; i <= n; i++)
      if (i >= s[j][0] && i <= s[j][1]) v[i].push_back(j);
  }
  for (int i = 1; i <= n; i++) {
    for (int j : add[i]) update(1, 1, n, s[j][0], s[j][1], -1);
    for (int j : rem[i]) update(1, 1, n, s[j][0], s[j][1], 1);
    int mx1 = query1(1, 1, n, 1, n);
    int mn1 = query2(1, 1, n, 1, n);
    if (mx1 - mn1 > mx) {
      mx = mx1 - mn1;
      z = i;
    }
  }
  cout << mx << endl << v[z].size() << endl;
  for (int j : v[z]) cout << j << " ";
}
