#include <bits/stdc++.h>
using namespace std;
//
const int mx = 1e5 + 5;
const int S = 320;
//
struct query
{
    int l, r, id;
    //
    bool operator < (const query &other)
    {
        if (l / S != other.l / S)
            return l < other.l;
        return l / S & 1 ? r < other.r : r > other.r;
    }
};
struct Fenwick_Tree
{
    int bit[mx];
    //
    void update (int idx, int val)
    {
        if (idx == 0)
            return;
        for (; idx < mx; idx += idx & -idx)
            bit[idx] += val;
    }
    int sum (int idx)
    {
        int res = 0;
        //
        for (; idx > 0; idx -= idx & -idx)
            res += bit[idx];
        return res;
    }
    int get (int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};
//
int n, q, P[mx];
long long ans[mx];
query Q[mx];
Fenwick_Tree FT;
//
void calc (void)
{
    int l = 0, r = 0;
	long long res = 0;
    //
    for (int i = 1; i <= q; ++i)
    {
        while (l < Q[i].l)
        {
            FT.update(P[l], -1);
            res -= FT.get(1, P[l]);
            ++l;
        }
        while (l > Q[i].l)
        {
            --l;
            res += FT.get(1, P[l]);
            FT.update(P[l], 1);
        }
        while (r < Q[i].r)
        {
            ++r;
            res += FT.get(P[r], n);
            FT.update(P[r], 1);
        }
        while (r > Q[i].r)
        {
            FT.update(P[r], -1);
            res -= FT.get(P[r], n);
            --r;
        }
        ans[Q[i].id] = res;
    }
}
//
void process (void)
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> P[i];
    for (int i = 1; i <= q; ++i)
        cin >> Q[i].l >> Q[i].r,
        Q[i].id = i;

    sort(Q + 1, Q + q + 1);
    calc();

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
}
//
signed main (void)
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    process();
}