#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q, a[N], l[N], r[N], L[N], R[N], s[N], t, ans[N], ar[N];
vector<int> f[N];
vector<pair<int, int>> ad[N], qu[N];
struct fenwick
{
    int n, c[N];
    void init(int m) 
    {
        n = m;
        for(int i = 1; i <= n; i++) c[i] = 0;
    }
    void add(int x, int v) {for(; x <= n; x += x & (-x)) c[x] += v;}
    int ask(int x) 
    {
        int ans = 0;
        for(; x; x -= x & (-x)) ans += c[x];
        return ans;
    }
    void add(int l, int r, int v) {add(l, v), add(r + 1, -v);}
}bt;
int main()
{
    ios :: sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i]; f[a[i]].push_back(i);
        while(t && a[s[t]] >= a[i]) r[s[t--]] = i;
        l[i] = s[t], s[++t] = i;
    }
    while(t) r[s[t--]] = n + 1;
    for(int i = 0; i <= n + 1; i++) L[i] = i - 1, R[i] = min(n + 1, i + 1);
    for(int o = 1; o <= n; o++) 
    {
        reverse(begin(f[o]), end(f[o]));
        for(int u: f[o]) 
        {
            R[L[u]] = R[u], L[R[u]] = L[u];
            if(a[R[u]] == a[u]) R[u] = R[R[u]];
        }
        for(int u: f[o]) 
        {
            if(a[r[u]] == a[u]) ar[u] = R[ar[r[u]]];
            else ar[u] = R[r[u] - 1];
            ad[l[u] + 1].emplace_back(u, ar[u] - 1);
            ad[u + 1].emplace_back(-u, ar[u] - 1);
        }
    }
    for(int i = 1; i <= q; i++) 
    {
        int l, r; cin >> l >> r;
        qu[l].emplace_back(r, i);
    }
    bt.init(n);
    for(int i = 1; i <= n; i++) 
    {
        for(auto [l, r]: ad[i])
        {
            if(l > 0) bt.add(l, r, 1);
            else l = -l, bt.add(l, r, -1); 
        } 
        for(auto [r, id]: qu[i]) ans[id] = r - i + 1 - bt.ask(r);
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}