#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chmin(T &x, const T &y) {
  if (x > y) x = y;
}
template <typename T>
void chmax(T &x, const T &y) {
  if (x < y) x = y;
}
int read() {
  char c;
  while ((c = getchar()) < '-')
    ;
  if (c == '-') {
    int x = (c = getchar()) - '0';
    while ((c = getchar()) >= '0') x = x * 10 + c - '0';
    return -x;
  }
  int x = c - '0';
  while ((c = getchar()) >= '0') x = x * 10 + c - '0';
  return x;
}
const int N = 120000 + 5;
int n, p[N], dy[N];
vector<int> lkq[N];
int qr[N];
long long qans[N];
namespace SEG {
const int T = N * 4;
int mn[T], ad[T], mn_cnt[T], ad_cnt[T];
long long tot_cnt[T];
void add(int k, int w) {
  mn[k] += w;
  ad[k] += w;
}
void add2(int k, int c) {
  tot_cnt[k] += (long long)c * mn_cnt[k];
  ad_cnt[k] += c;
}
void down(int k) {
  add((k * 2), ad[k]);
  add(((k * 2) + 1), ad[k]);
  ad[k] = 0;
  if (mn[(k * 2)] == mn[k]) add2((k * 2), ad_cnt[k]);
  if (mn[((k * 2) + 1)] == mn[k]) add2(((k * 2) + 1), ad_cnt[k]);
  ad_cnt[k] = 0;
}
void up(int k) {
  if (mn[(k * 2)] != mn[((k * 2) + 1)]) {
    int x = mn[(k * 2)] < mn[((k * 2) + 1)] ? (k * 2) : ((k * 2) + 1);
    mn[k] = mn[x];
    mn_cnt[k] = mn_cnt[x];
  } else {
    mn[k] = mn[(k * 2)];
    mn_cnt[k] = mn_cnt[(k * 2)] + mn_cnt[((k * 2) + 1)];
  }
  tot_cnt[k] = tot_cnt[(k * 2)] + tot_cnt[((k * 2) + 1)];
}
void suf_add(int i, int w) {
  int k = 1, l = 1, r = n;
  while (l != r) {
    down(k);
    if (i <= ((l + r) / 2)) {
      add(((k * 2) + 1), w);
      k = (k * 2);
      r = ((l + r) / 2);
    } else {
      k = ((k * 2) + 1);
      l = ((l + r) / 2) + 1;
    }
  }
  add(k, w);
  while (k >>= 1) up(k);
}
void calc(int k) {
  if (mn[k] == 0) add2(k, 1);
}
void suf_calc(int i) {
  int k = 1, l = 1, r = n;
  while (l != r) {
    down(k);
    if (i <= ((l + r) / 2)) {
      calc(((k * 2) + 1));
      k = (k * 2);
      r = ((l + r) / 2);
    } else {
      k = ((k * 2) + 1);
      l = ((l + r) / 2) + 1;
    }
  }
  calc(k);
  while (k >>= 1) up(k);
}
long long qiu(int i) {
  if (i > n) return 0;
  long long ans = 0;
  int k = 1, l = 1, r = n;
  while (l != r) {
    down(k);
    if (i <= ((l + r) / 2)) {
      ans += tot_cnt[((k * 2) + 1)];
      k = (k * 2);
      r = ((l + r) / 2);
    } else {
      k = ((k * 2) + 1);
      l = ((l + r) / 2) + 1;
    }
  }
  return ans + tot_cnt[k];
}
};  // namespace SEG
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) dy[p[i] = read()] = i;
  int m = read();
  for (int i = 1; i <= m; ++i) {
    lkq[read()].push_back(i);
    qr[i] = read();
  }
  for (int i = 1; i <= n * 4; ++i) SEG::mn_cnt[i] = 1;
  for (int i = n; i >= 1; --i) {
    if (i < n) SEG::suf_add(i + 1, 1);
    if (i < dy[p[i] - 1]) SEG::suf_add(dy[p[i] - 1], -1);
    if (i < dy[p[i] + 1]) SEG::suf_add(dy[p[i] + 1], -1);
    SEG::suf_calc(i);
    for (auto x : lkq[i]) qans[x] = SEG::qiu(i) - SEG::qiu(qr[x] + 1);
  }
  for (int i = 1; i <= m; ++i) printf("%lld\n", qans[i]);
}
