#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int N = 1005;
int n, m, a[N], c[N];
struct Node{
    int x,id;
}f[N];
bool cmp(Node a,Node b) {
    return a.x < b.x;
}
int num,now1,now2,now;
int ans[N][N];
void insert(int x) {
    for (int i = x; i <= n; i += i & -i)    ++c[i];
}
int sum(int x) {
    int ans = 0;
    for (int i = x; i; i -= i & -i) ans += c[i];
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) f[i].x = a[i];
    for (int i = 1; i <= n; ++i) f[i].id = i;
    sort(f + 1, f + n + 1, cmp);
    num = 0;
    now1 = 1;
    while (now1 <= n) {
        now2 = now1;
        ++num;
        while (now2 <= n && f[now2].x == f[now1].x) {
            a[f[now2].id] = num;
            ++now2;
        }
        now1 = now2;
    }
    for (int i = 1; i <= n; ++i) {
        memset(c, 0, sizeof(c));
        now = 0;
        for (int j = i; j <= n; ++j) {
            now += sum(n) - sum(a[j]);
            insert(a[j]);
            ans[i][j] = now;
        }
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &now1, &now2);
        printf("%d\n", ans[now1][now2]);
    }
    return 0;
}