#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
const int N = 1e5 + 10;
#define pi pair<int, int>
#define l first
#define op second
struct node {
  int sum, c[2];
} t[N * 20];
int cnt;
int n, K, ql, qr, pos[N];
int p[N];
int tot, rt[N], mp[N];
int cur, np;
vector<pi> s[N];
void Build(int &x, int l, int r) {
  x = ++cnt;
  if (l == r) return;
  int mid = (l + r >> 1);
  Build(t[x].c[0], l, mid), Build(t[x].c[1], mid + 1, r);
}
void Upd(int x) { t[x].sum = t[t[x].c[0]].sum + t[t[x].c[1]].sum; }
void Ins(int &x, int y, int l, int r, int id, int v) {
  x = ++cnt;
  if (l == r) return (void)(t[x].sum = t[y].sum + v);
  int mid = (l + r >> 1);
  if (id <= mid) {
    t[x].c[1] = t[y].c[1], Ins(t[x].c[0], t[y].c[0], l, mid, id, v);
  } else {
    t[x].c[0] = t[y].c[0], Ins(t[x].c[1], t[y].c[1], mid + 1, r, id, v);
  }
  Upd(x);
}
int Que(int x, int l, int r, int id) {
  if (r < id) return 0;
  if (l >= id) return t[x].sum;
  int mid = (l + r >> 1);
  return Que(t[x].c[0], l, mid, id) + Que(t[x].c[1], mid + 1, r, id);
}
void Answer(int rs, int lp) {
  cout << 1ll * n * rs - (n - lp) << "\n";
  cout << flush;
}
int main() {
#ifdef memset0
  freopen("K.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> K;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    pos[p[i]] = i;
  }
  cur = 1;
  for (int i = 1; i < n; ++i) {
    if (pos[i + 1] < pos[i]) {
      s[pos[i]].push_back((pi){pos[i + 1], -1});
      ++cur;
    } else
      s[pos[i + 1]].push_back((pi){pos[i], 1});
  }
  Build(rt[0], 1, n);
  for (int i = 1; i <= n; ++i) {
    for (pi j : s[i]) {
      Ins(rt[tot + 1], rt[tot], 1, n, j.l, j.op);
      ++tot;
    }
    mp[i] = tot;
  }
  Answer(cur, pos[n]);
  while (K--) {
    cin >> ql >> qr;
    if (ql <= pos[n] && pos[n] <= qr) np = ql + qr - pos[n];
    else {
      np = pos[n];
    }
    Answer(cur + Que(rt[mp[qr]], 1, n, ql), np);
  }
}