#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T maxi(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
inline T mini(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
inline T absl(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  if (a < b) {
    while (a) {
      t = a;
      a = b % a;
      b = t;
    }
    return b;
  } else {
    while (b) {
      t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}
template <typename T>
inline T ceiling(T a, T b) {
  if (a % b == 0) return (a / b);
  return ((a / b) + 1);
}
int n;
vector<int> b(500000);
int UPDATE_RANGE(int l, int r, int diff) {
  --l;
  --r;
  for (int i = l; i <= r; ++i) {
    b[i] += diff;
  }
}
int GETMIN(int s, int f) {
  int ans = INT_MIN;
  for (int i = 0; i < n; ++i) ans = maxi(ans, b[i]);
  return ans;
}
void input() {
  int m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  for (long long int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  int l[m], r[m];
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &l[i], &r[i]);
    --l[i];
    --r[i];
  }
  vector<int> start[n], finish[n];
  for (int i = 0; i < m; ++i) {
    start[l[i]].push_back(i);
    finish[r[i]].push_back(i);
  }
  int max1 = *max_element(a.begin(), a.end());
  max1 -= *min_element(a.begin(), a.end());
  int index = -1;
  int z = start[0].size();
  for (auto it = start[0].begin(); it != start[0].end(); ++it) {
    int x = (*it);
    UPDATE_RANGE(l[x] + 1, r[x] + 1, -1);
  }
  int y = (GETMIN(1, n) - a[0] + z);
  if (y > max1) {
    index = 0;
    max1 = y;
  }
  for (int i = 1; i < n; ++i) {
    for (auto it : start[i]) {
      UPDATE_RANGE(l[it] + 1, r[it] + 1, -1);
    }
    for (auto it : finish[i - 1]) UPDATE_RANGE(l[it] + 1, r[it] + 1, 1);
    z += (start[i].size() - finish[i - 1].size());
    int x = (GETMIN(1, n) - a[i] + z);
    if (max1 < x) {
      max1 = x;
      index = i;
    }
  }
  cout << max1 << endl;
  if (index == -1) {
    cout << 0 << endl;
    return;
  }
  vector<int> c;
  for (int i = 0; i < m; ++i) {
    if (index >= l[i] && index <= r[i]) c.push_back(i + 1);
  }
  cout << c.size() << endl;
  for (auto it : c) cout << it << " ";
  cout << endl;
}
int main() {
  input();
  return 0;
}
