#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int arr[501000], idx[501000], a[501000], A;
int n, Q, x1, x2;
long long ans[501000];
vector<P> q[501000];
P &operator+=(P &p, const int &x) {
  p.first += x;
  return p;
}
P operator+(const P &x, const P &y) {
  P ret = {min(x.first, y.first), 0};
  if (ret.first == x.first) ret.second += x.second;
  if (ret.first == y.first) ret.second += y.second;
  return ret;
}
struct Segment_tree {
  P val[501000 << 2];
  int tag1[501000 << 2], tag2[501000 << 2];
  long long cnt[501000 << 2];
  inline void pushup(int x) {
    val[x] = val[(x << 1)] + val[(x << 1 | 1)];
    cnt[x] = cnt[(x << 1)] + cnt[(x << 1 | 1)];
  }
  inline void upd1(int x, int Val) {
    val[x] += Val;
    tag1[x] += Val;
  }
  inline void upd2(int x, long long Val) {
    cnt[x] += val[x].second * Val;
    tag2[x] += Val;
  }
  inline void pushdown(int x) {
    if (tag1[x]) {
      upd1((x << 1), tag1[x]);
      upd1((x << 1 | 1), tag1[x]);
      tag1[x] = 0;
    }
    if (tag2[x]) {
      if (val[(x << 1)].first == val[x].first) upd2((x << 1), tag2[x]);
      if (val[(x << 1 | 1)].first == val[x].first) upd2((x << 1 | 1), tag2[x]);
      tag2[x] = 0;
    }
  }
  inline void build(int x, int l, int r) {
    val[x] = {0, 1};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build((x << 1), l, mid);
    build((x << 1 | 1), mid + 1, r);
    pushup(x);
    return;
  }
  void modify1(int x, int l, int r, int lx, int rx, int T) {
    if (lx <= l && r <= rx) {
      return upd1(x, T);
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (lx <= mid) modify1((x << 1), l, mid, lx, rx, T);
    if (rx > mid) modify1((x << 1 | 1), mid + 1, r, lx, rx, T);
    pushup(x);
  }
  void modify2(int x, int l, int r, int lx, int rx, int T) {
    if (val[x].first > 1) return;
    if (lx <= l && r <= rx) {
      return upd2(x, T);
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (lx <= mid) modify2((x << 1), l, mid, lx, rx, T);
    if (rx > mid) modify2((x << 1 | 1), mid + 1, r, lx, rx, T);
    pushup(x);
  }
  long long query(int x, int l, int r, int lx, int rx) {
    if (lx <= l && r <= rx) return cnt[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (lx <= mid) ans += query((x << 1), l, mid, lx, rx);
    if (rx > mid) ans += query((x << 1 | 1), mid + 1, r, lx, rx);
    return ans;
  }
} tree;
inline int read() {
  int x = 0;
  char c = getchar();
  bool y = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') y = 0;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - 48;
  if (y) return x;
  return -x;
}
inline void Input() {
  n = read();
  for (int i = 1; i <= n; i++) idx[arr[i] = read()] = i;
  Q = read();
  for (int i = 1; i <= Q; i++) {
    int x1 = read(), x2 = read();
    q[x2].push_back(make_pair(x1, i));
  }
  return;
}
inline void solve() {
  tree.build(1, 1, n);
  for (register int i = 1; i <= n; i++) {
    tree.modify1(1, 1, n, 1, i, 1);
    if (arr[i] > 1 && idx[arr[i] - 1] < i)
      tree.modify1(1, 1, n, 1, idx[arr[i] - 1], -1);
    if (arr[i] < n && idx[arr[i] + 1] < i)
      tree.modify1(1, 1, n, 1, idx[arr[i] + 1], -1);
    tree.modify2(1, 1, n, 1, i, 1);
    for (unsigned int j = 0; j < q[i].size(); ++j) {
      int Se = q[i][j].second, Fi = q[i][j].first;
      ans[Se] = tree.query(1, 1, n, Fi, i);
    }
  }
  for (register int i = 1; i <= Q; i++) {
    printf("%lld\n", ans[i]);
  }
  return;
}
signed main() {
  Input();
  solve();
  return 0;
}
