// Problem : LFIVES
// Complexity : O(N^2 logN + Q)
// Author : Gedi Zheng
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
using std::vector;

int n, q, lim;
int a[2022];
int tree[4][2022], ans[2022][2022];

void Init() {
  assert(scanf("%d%d", &n, &q) == 2);
  vector<int> axis;
  axis.push_back(-1);
  for (int i = 0; i < n; ++i) {
    assert(scanf("%d", a + i) == 1);
    axis.push_back(a[i]);
  }
  // Compress the data
  std::sort(axis.begin(), axis.end());
  axis.erase(std::unique(axis.begin(), axis.end()), axis.end());
  lim = axis.size() + 1;
  for (int i = 0; i < n; ++i)
    a[i] = std::lower_bound(axis.begin(), axis.end(), a[i]) - axis.begin();
}

inline int Lowbit(int x) {
  return x & -x;
}

void Insert(int x, int v, int tree[]) {
  for ( ; x < lim; x += Lowbit(x))
    tree[x] += v;
}

int Query(int x, int tree[]) {
  int ret = 0;
  for ( ; x; x -= Lowbit(x))
    ret += tree[x];
  return ret;
}

void Work() {
  // Maintain four Fenwick Tree and pre-compute the answer of all possible queries
  for (int l = 0; l < n; ++l) {
    memset(tree, 0, sizeof(tree));
    Insert(lim - a[l], 1, tree[0]);
    for (int j = l + 1; j < n; ++j) {
      ans[l][j] = Query(a[j] - 1, tree[3]);
      Insert(a[j], Query(lim - a[j] - 1, tree[2]), tree[3]);
      Insert(lim - a[j], Query(a[j] - 1, tree[1]), tree[2]);
      Insert(a[j], Query(lim - a[j] - 1, tree[0]), tree[1]);
    }
  }
  // Answer the queries
  while (q--) {
    int l, r;
    assert(scanf("%d%d", &l, &r) == 2);
    --l; --r;
    printf("%d\n", ans[l][r]);
  }
}

int main() {
  Init();
  Work();
  return 0;
}