#include <bits/stdc++.h>
using namespace std;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 1.2e5 + 5;
const int INF = 1e9;
int n, q;
int a[N];
long long ans[N];
int be[N], B;
struct QUERY {
  int l, r, id;
  QUERY(const int l_ = 0, const int r_ = 0, const int id_ = 0) {
    l = l_;
    r = r_;
    id = id_;
  }
  friend bool operator<(QUERY a, QUERY b) { return a.id < b.id; }
};
set<QUERY> s[N];
struct block {
  int mv, tot, ad, tim;
  long long pv;
} blk[N];
int val[N];
int vt[N];
int lef[N], rig[N];
void rebuild(int x) {
  for (int i = lef[x]; i <= rig[x]; i++) val[i] = val[i] + blk[x].ad;
  if (blk[x].tim)
    for (int i = lef[x]; i <= rig[x]; i++)
      if (val[i] == blk[x].mv) vt[i] += blk[x].tim;
  blk[x].ad = blk[x].tot = blk[x].tim = 0;
  blk[x].mv = INF;
  for (int i = lef[x]; i <= rig[x]; i++) {
    if (blk[x].mv > val[i]) blk[x].mv = val[i], blk[x].tot = 0;
    if (blk[x].mv == val[i]) blk[x].tot++;
  }
}
void add(int l, int r, int v) {
  if (be[l] == be[r]) {
    rebuild(be[l]);
    for (int i = l; i <= r; i++) val[i] = val[i] + v;
    rebuild(be[l]);
    return;
  }
  for (int i = be[l] + 1; i <= be[r] - 1; i++) {
    blk[i].ad = blk[i].ad + v;
    blk[i].mv = blk[i].mv + v;
  }
  rebuild(be[l]);
  for (int i = l; i <= rig[be[l]]; i++) val[i] = val[i] + v;
  rebuild(be[l]);
  rebuild(be[r]);
  for (int i = lef[be[r]]; i <= r; i++) val[i] = val[i] + v;
  rebuild(be[r]);
}
long long query(int l, int r) {
  long long ret = 0;
  if (be[l] == be[r]) {
    rebuild(be[l]);
    for (int i = l; i <= r; i++) ret += vt[i];
    return ret;
  }
  for (int i = be[l] + 1; i <= be[r] - 1; i++) ret = ret + blk[i].pv;
  rebuild(be[l]);
  rebuild(be[r]);
  for (int i = l; i <= rig[be[l]]; i++) ret = ret + vt[i];
  for (int i = lef[be[r]]; i <= r; i++) ret = ret + vt[i];
  return ret;
}
void update() {
  for (int i = 1; i <= be[n]; i++)
    if (blk[i].mv == 0) blk[i].pv = blk[i].pv + blk[i].tot, blk[i].tim++;
}
struct Decreasing_Stack {
  int len, a[N], w[N];
  void init() { len = 0; }
  void pushback(int x, int p) {
    while (len && a[len] < x) {
      add(w[len - 1] + 1, w[len], -a[len]);
      len--;
    }
    add(w[len] + 1, p, x);
    a[++len] = x;
    w[len] = p;
  }
} Max, Min;
int main() {
  n = get();
  for (int i = 1; i <= n; i++) a[i] = get();
  q = get();
  for (int i = 1; i <= q; i++) {
    int l = get(), r = get();
    s[r].insert(QUERY(l, r, i));
  }
  B = sqrt(n) + 1;
  for (int i = 1; i <= n; i++) be[i] = (i - 1) / B + 1;
  for (int i = 1; i <= n; i++) rig[be[i]] = i;
  for (int i = n; i >= 1; i--) lef[be[i]] = i;
  for (int i = 1; i <= n; i++) val[i] = INF;
  Max.init();
  Min.init();
  for (int i = 1; i <= be[n]; i++) rebuild(i);
  for (int i = 1; i <= n; i++) {
    Max.pushback(a[i], i);
    Min.pushback(-a[i], i);
    add(1, i, -1);
    rebuild(be[i]);
    val[i] = 0;
    rebuild(be[i]);
    update();
    for (set<QUERY>::iterator h = s[i].begin(); h != s[i].end(); h++)
      ans[(*h).id] = query((*h).l, (*h).r);
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}
