#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
const int MOD = 1e9 + 7;
int N, M, K, Q;
int L[310], R[310], A[310];
int diff[310], ori_seg[4 * 310], tmp[4 * 310];
vector<pair<int, int>> checks;
int update(int node, int low, int high, int pos, int val, int *seg) {
  if (high < pos || pos < low) return seg[node];
  if (low == high) return seg[node] += val;
  int mid = (low + high) / 2;
  return seg[node] = update(2 * node, low, mid, pos, val, seg) +
                     update(2 * node + 1, mid + 1, high, pos, val, seg);
}
int query(int node, int low, int high, int qlow, int qhigh, int *seg) {
  if (high < qlow || low > qhigh) return 0;
  if (qlow <= low && high <= qhigh) return seg[node];
  int mid = (low + high) / 2;
  return query(2 * node, low, mid, qlow, qhigh, seg) +
         query(2 * node + 1, mid + 1, high, qlow, qhigh, seg);
}
int main() {
  int i, j, k, u, v, x, y;
  scanf("%d%d", &N, &M);
  for (i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    checks.push_back({A[i], i});
  }
  sort(checks.begin(), checks.end());
  reverse(checks.begin(), checks.end());
  for (i = 1; i <= M; ++i) {
    scanf("%d%d", &L[i], &R[i]);
  }
  diff[1] = A[1];
  int sum = diff[1];
  for (i = 2; i <= N; ++i) {
    diff[i] = A[i] - sum;
    sum += diff[i];
  }
  for (i = 1; i <= N; ++i) {
    update(1, 1, N, i, diff[i], ori_seg);
  }
  int ans = -0x3f3f3f3f;
  int anssz = -1;
  vector<int> ansvec;
  for (k = 0; k < checks.size(); ++k) {
    int idx = checks[k].second;
    int cnt = 0;
    memcpy(tmp, ori_seg, sizeof(ori_seg));
    vector<int> vt;
    for (i = 1; i <= M; ++i) {
      if (idx < L[i] || R[i] < idx) {
        update(1, 1, N, L[i], -1, tmp);
        update(1, 1, N, R[i] + 1, +1, tmp);
        vt.push_back(i);
      }
    }
    int mini = 0x3f3f3f3f;
    int maxi = -0x3f3f3f3f;
    for (i = 1; i <= N; ++i) {
      mini = min(mini, query(1, 1, N, 1, i, tmp));
      maxi = max(maxi, query(1, 1, N, 1, i, tmp));
    }
    if (maxi - mini > ans) {
      ans = maxi - mini;
      anssz = vt.size();
      ansvec = vt;
    }
  }
  printf("%d\n%d\n", ans, anssz);
  for (i = 0; i < anssz; ++i) {
    printf("%d ", ansvec[i]);
  }
}
