#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int INF32 = 0x3f3f3f3f;
const long long INF64 = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
const double PI = acos(-1.0);
long long tree[MAXN << 2], add[MAXN << 2];
int arr[MAXN], l[310], r[310];
vector<int> vec[MAXN];
void intt() {
  memset(tree, 0, sizeof(tree));
  memset(add, 0, sizeof(add));
  memset(arr, 0, sizeof(arr));
  memset(l, 0, sizeof(l));
  memset(r, 0, sizeof(r));
  for (int i = 0; i < MAXN; ++i) vec[i].clear();
}
void build_tree(int l, int r, int rt) {
  if (l == r) {
    tree[rt] = arr[l];
    return;
  }
  int mid = (l + r) >> 1;
  build_tree(l, mid, rt << 1);
  build_tree(mid + 1, r, rt << 1 | 1);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
void push_down(int rt) {
  if (add[rt] != 0) {
    add[rt << 1] += add[rt];
    add[rt << 1 | 1] += add[rt];
    tree[rt << 1] += add[rt];
    tree[rt << 1 | 1] += add[rt];
    add[rt] = 0;
  }
}
void updata(int ql, int qr, int x, int l, int r, int rt) {
  if (ql <= l && qr >= r) {
    tree[rt] += x;
    add[rt] += x;
    return;
  }
  int mid = (l + r) >> 1;
  push_down(rt);
  if (ql <= mid) updata(ql, qr, x, l, mid, rt << 1);
  if (qr > mid) updata(ql, qr, x, mid + 1, r, rt << 1 | 1);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
int Query(int ql, int qr, int l, int r, int rt) {
  if (ql <= l && qr >= r) return tree[rt];
  int mid = (l + r) >> 1;
  push_down(rt);
  int res = -INF32;
  if (ql <= mid) res = Query(ql, qr, l, mid, rt << 1);
  if (qr > mid) res = Query(ql, qr, mid + 1, r, rt << 1 | 1);
  return res;
}
void Show(int l, int r, int rt) {
  if (l == r) {
    cout << "point: " << l << ": " << tree[rt] << endl;
    return;
  }
  int mid = (l + r) >> 1;
  Show(l, mid, rt << 1);
  Show(mid + 1, r, rt << 1 | 1);
}
int main() {
  int n, m;
  while (cin >> n >> m) {
    intt();
    for (int i = 1; i <= n; ++i) {
      cin >> arr[i];
    }
    for (int i = 1; i <= m; ++i) {
      cin >> l[i] >> r[i];
      vec[l[i]].push_back(i);
      vec[r[i] + 1].push_back(-i);
    }
    int ans = -INF32, ansi;
    build_tree(1, n, 1);
    for (int i = 1; i <= n; ++i) {
      int len = vec[i].size();
      for (int j = 0; j < len; ++j) {
        int x = vec[i][j];
        if (x > 0)
          updata(l[x], r[x], -1, 1, n, 1);
        else
          updata(l[-x], r[-x], 1, 1, n, 1);
      }
      int maxx = Query(1, n, 1, n, 1);
      int minn = Query(i, i, 1, n, 1);
      if (maxx - minn > ans) {
        ans = maxx - minn;
        ansi = i;
      }
    }
    int k = 0;
    for (int i = 1; i <= m; ++i) {
      if (l[i] <= ansi && r[i] >= ansi) k++;
    }
    cout << ans << endl << k << endl;
    for (int i = 1; i <= m; ++i) {
      if (l[i] <= ansi && r[i] >= ansi) cout << i << " ";
    }
    cout << endl;
  }
}
