// LFIVES
// Lucky Fives
// Author: Constantine Sokol
// Complexity : O(N ^ 2 * log N + Q log Q)
// Expected Verdict: AC

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 2020;
const int MAXQ = 100100;

int n, q, a[MAXN], max_value;
int f[6][MAXN];
int fw[6][MAXN];
pair<int, int> buf[MAXN];
pair<int, int> queries[MAXQ];
int queries_order[MAXQ];
int queries_answer[MAXQ];

void compress(int a[], int n) {
    for (int i = 1; i <= n; i++) {
        buf[i] = make_pair(a[i], i);
    }
    sort(buf + 1, buf + n + 1);
    int last_key = -1, value = 0;
    for (int i = 1; i <= n; i++) {
        if (last_key < buf[i].first) {
            last_key = buf[i].first;
            value = value + 1;
        }
        a[buf[i].second] = value;
    }
    max_value = value;
}

int fsum(int fw[], int pos) {
    int result = 0;
    while (pos) {
        result += fw[pos];
        pos = pos & (pos - 1);
    }
    return result;
}

void modify(int fw[], int pos, int delta) {
    while (pos <= max_value) {
        fw[pos] += delta;
        pos = pos + pos - (pos & (pos - 1) ); 
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i] );
    compress(a, n);

    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        queries[i] = make_pair(l, r);
        queries_order[i] = i;
    }
    sort(queries_order + 1, queries_order + q + 1, 
        [](int a, int b) {
            return queries[a] < queries[b];
        } );

    int ptr = 1;

    for (int l = 1; l <= n; l++) {
        memset(f, 0, sizeof(f) );
        memset(fw, 0, sizeof(fw) );

        f[1][l] = 1;
        modify(fw[1], a[l], f[1][l] );

        for (int r = l; r <= n; r++) {
            for (int k = 2; k <= 5; k++) {
                if (k % 2) {
                    f[k][r] = fsum(fw[k - 1], a[r] - 1);
                } else {
                    f[k][r] = fsum(fw[k - 1], max_value) - fsum(fw[k - 1], a[r] );
                }
                modify(fw[k], a[r], f[k][r] );
            }

            while (true) {
                if (ptr == q + 1) {
                    break;
                }
                if (queries[queries_order[ptr] ] > make_pair(l, r) ) {
                    break;
                }
                queries_answer[queries_order[ptr] ] = f[5][r];
                ptr += 1;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        printf("%d\n", queries_answer[i] );
    }
    return 0;
}