#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5;

#define lsb(x) (x & -x)

struct AIB {
   vector<int> tree;
   void init(int n) {
      tree.assign(n + 2, 0);
   }
   void upd(int p, int x) {
      p++;
      while(p < sz(tree)) tree[p] += x, p += lsb(p);
   }
   int query(int p) {
      p++;
      int sum = 0;
      while(p > 0) sum += tree[p], p -= lsb(p);
      return sum;
   }
} aib;

int sum[nmax];
void add(int p, int x) {
   aib.upd(p, x);
}
int query(int l, int r) {
   int total = r - l + 1;
   return total + aib.query(r) - aib.query(l - 1);
}

template<typename Node>
struct AINT {
   vector<Node> aint;
   int n;
   void init(int n_, Node TMP = Node()) {
      n = n_;
      aint.assign(2 * n + 10, TMP);
   }
   template<class CB> void walk(CB&& cb) { walk(cb, 0, n - 1); }
   template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 0, n - 1); }
   template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) { 
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      
      int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
      walk(cb, l, r, L, cl, mid);
      walk(cb, l, r, L, mid + 1, cr);
      aint[node].pull(aint[L], aint[R]);
   }
};

struct Node {
   int mx;
   void pull(Node& L, Node& R) {
      *this = Node(max(L.mx, R.mx));
   }
};

vector<pii> qs[nmax];
int rez[nmax];

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, q;
   cin >> n >> q;
   aib.init(n + 1);

   vector<int> v(n);
   for(auto &x : v) cin >> x;
   
   AINT<Node> aint;
   aint.init(n);
   
   aint.walk([&](Node& val, int cl, int cr) {
      if(cl != cr) return 1;
      val.mx = v[cl];
      return 0;
   });
   
   auto nxt_gval = [&](int p, int target) {
      if(p >= n) return n;
      //cerr << p << ' ' << target << '\t'; cerr << val.mx << ", " << cl << " ~ " << cr << '\n'; 
      p++;
      int rez = p;
      aint.walk([&](Node& val, int cl, int cr) {
         if(cr < rez) return 0;
         if(rez < cl) return 0;
         if(val.mx <= target) { rez = cr + 1; return 0;}
         if(cl == cr) {
            rez = cl;
             return 0;
         }
         return 1;
      }, p, n - 1);
      
      //cerr << rez << '\n';
      return rez;
   };

   
   for(int tc = 0, l, r; tc < q; tc++) {
      cin >> l >> r;
      --l;
      --r;
      qs[l].emplace_back(r, tc);
   }
   
   
   struct st_elem {
      int val;
      int poz;
      int borderpoz;
   };
   vector<st_elem> st;
   
   for(int i = n - 1; i >= 0; i--) {
      while(!st.empty() && st.back().val > v[i]) {
         add(st.back().poz, 1);
         add(st.back().borderpoz, -1);
         st.pop_back();
      }
      
      add(i, -1);
      
      if(st.empty())
         st.emplace_back(v[i], i, n);
      else
         st.emplace_back(v[i], i, nxt_gval(st.back().val == v[i]? st.back().borderpoz : st.back().poz, v[i]));
      
      add(st.back().borderpoz, 1);
      
      for(auto [r, ptr] : qs[i])
         rez[ptr] = query(i, r);
   }
   
   for(int i = 0; i < q; i++) cout << rez[i] << '\n';
   
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/