#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

const int N = 1e5 + 5, K = 325;

int n, m, B, blockOf[N];
int a[N], b[N], diff;
int f[N], g[N];
long long ans[N];

struct Segment
{
    Segment() {}
    Segment(int id, int l, int r, int neg, int type)
        : id(id), l(l), r(r), neg(neg), type(type){}
    int id, l, r;
    int neg, type;
};
std::vector<Segment> seg[N];

struct Query
{
    int l, r, id;
    long long tRes;

    bool operator<(const Query &comp) const
    {
        if (blockOf[l] == blockOf[comp.l])
            return r < comp.r;
        return blockOf[l] < blockOf[comp.l];
    }
} q[N];

class BlockSequence
{
private:
    int bSize, len, count[N], add[K];

public:
    void Init(int length)
    {
        len = length;
        bSize = std::sqrt(len);
    }

    void Add(int pos)
    {
        while (pos <= len && pos % bSize != 0)
        {
            count[pos]++;
            pos++;
        }
        if (pos > len)
            return;
        int bPos = pos / bSize;
        while (bPos * bSize <= len)
        {
            add[bPos]++;
            bPos++;
        }
    }

    int Query(int pos)
    {
        return count[pos] + add[pos / bSize];
    }
} seq;

class BinaryIndexedTree
{
private:
    inline int LowBit(int x) { return x & (-x); }
    int count[N];

public:
    void Add(int pos)
    {
        while (pos <= diff)
        {
            count[pos]++;
            pos += LowBit(pos);
        }
    }

    int Query(int pos)
    {
        int res = 0;
        while (pos > 0)
        {
            res += count[pos];
            pos ^= LowBit(pos);
        }
        return res;
    }
} tree;

int GetIndexOf(int x)
{
    int l = 1, r = diff;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (b[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

void Init()
{
    std::sort(b + 1, b + n + 1);
    diff = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++)
        a[i] = GetIndexOf(a[i]);

    for (int i = 1; i <= n; i++)
    {
        f[i] = tree.Query(a[i] - 1);
        tree.Add(a[i]);
        g[i] = i - tree.Query(a[i]);
    }
    seq.Init(diff);

    std::sort(q + 1, q + m + 1);
}

void Solve()
{
    for (int i = 1, l = 1, r = 0; i <= m; i++)
    {
        if (l > q[i].l)
            seg[r].push_back(Segment(i, q[i].l, l - 1, 1, 0));
        while (l > q[i].l)
            q[i].tRes -= f[--l];

        if (r < q[i].r)
            seg[l - 1].push_back(Segment(i, r + 1, q[i].r, -1, 1));
        while (r < q[i].r)
            q[i].tRes += g[++r];

        if (l < q[i].l)
            seg[r].push_back(Segment(i, l, q[i].l - 1, -1, 0));
        while (l < q[i].l)
            q[i].tRes += f[l++];

        if (r > q[i].r)
            seg[l - 1].push_back(Segment(i, q[i].r + 1, r, 1, 1));
        while (r > q[i].r)
            q[i].tRes -= g[r--];
    }

    for (int i = 1; i <= n; i++)
    {
        seq.Add(a[i]);
        for (Segment s : seg[i])
            for (int j = s.l; j <= s.r; j++)
            {
                if (s.type == 0)
                    q[s.id].tRes += seq.Query(a[j] - 1) * s.neg;
                else
                    q[s.id].tRes += (i - seq.Query(a[j])) * s.neg;
            }
    }

    for (int i = 1; i <= m; i++)
        q[i].tRes += q[i - 1].tRes;
    for (int i = 1; i <= m; i++)
        ans[q[i].id] = q[i].tRes;
}

int main()
{
    std::ios::sync_with_stdio(false);

    std::cin >> n >> m;
    B = std::sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        blockOf[i] = (i - 1) / B + 1;
        b[i] = a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        std::cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    Init();
    Solve();

    for (int i = 1; i <= m; i++)
        std::cout << ans[i] << '\n';
    return 0;
}