#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define ll long long
#define mst(a,x) memset(a,x,sizeof(a))
#define N 1005
using namespace std;

int c[N], ans[N][N];
struct node
{
    int x, p;
    node(int x = 0, int p = 0): x(x), p(p){}
    friend bool operator < (node a, node b)
    {
        return a.x < b.x;
    }
}b[N];
int n, q, cur, a[N];

void insert(int x)
{
    while(x <= n)
    {
        c[x]++;
        x += x & (-x);
    }
}

int sum(int x)
{
    int ret = 0;
    while(x >= 1)
    {
        ret += c[x];
        x -= x & (-x);
    }
    return  ret;
}

int main()
{
    int x, y;

    while(~scanf("%d%d", &n, &q))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &b[i].x);
            b[i].p = i;
        }
        sort(b, b + n);
        cur = 0;
        for(int i = 0; i < n; i++)
        {
            if(!i || b[i].x != b[i - 1].x) a[b[i].p] = ++cur;
            else a[b[i].p] = cur;
        }

        mst(ans, 0);
        for(int i = 0; i < n; i++)
        {
            mst(c, 0);
            insert(a[i]);
            for(int j = i + 1; j < n; j++)
            {
                ans[i][j] = ans[i][j - 1] + j - i - sum(a[j]);
                insert(a[j]);
            }
        }
        while(q--)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", ans[x - 1][y - 1]);
        }
    }
    return 0;
}