#include <bits/stdc++.h>
using namespace std;
long long N, Q, A[120005], mn[120005 << 2], ans[120005];
long long sum[120005 << 2], nd[120005 << 2], lz[120005 << 2];
long long siz[120005 << 2], tim[120005 << 2];
vector<pair<long long, long long> > ques[120005];
struct node {
  long long v, l, r;
};
stack<node> smx, smn;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
inline void pushup(long long k) {
  if (mn[k << 1] == mn[k << 1 | 1])
    mn[k] = mn[k << 1], siz[k] = siz[k << 1] + siz[k << 1 | 1];
  else if (mn[k << 1] < mn[k << 1 | 1])
    mn[k] = mn[k << 1], siz[k] = siz[k << 1];
  else
    mn[k] = mn[k << 1 | 1], siz[k] = siz[k << 1 | 1];
  sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
inline void pushdown(long long k) {
  if (lz[k]) {
    lz[k << 1] += lz[k], lz[k << 1 | 1] += lz[k];
    mn[k << 1] += lz[k], mn[k << 1 | 1] += lz[k];
    lz[k] = 0;
  }
  if (nd[k]) {
    if (mn[k << 1] == mn[k])
      sum[k << 1] += siz[k << 1] * nd[k], nd[k << 1] += nd[k];
    if (mn[k << 1 | 1] == mn[k])
      sum[k << 1 | 1] += siz[k << 1 | 1] * nd[k], nd[k << 1 | 1] += nd[k];
    nd[k] = 0;
  }
}
inline void build(long long l, long long r, long long k) {
  if (l == r) {
    mn[k] = 0x7fffffff, siz[k] = 1;
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
  pushup(k);
  return;
}
inline void add(long long l, long long r, long long x, long long y, long long v,
                long long t, long long k) {
  if (x <= l && r <= y) {
    mn[k] += v, lz[k] += v;
    return;
  }
  pushdown(k);
  long long mid = l + r >> 1;
  if (x <= mid) add(l, mid, x, y, v, t, k << 1);
  if (y > mid) add(mid + 1, r, x, y, v, t, k << 1 | 1);
  pushup(k);
  return;
}
inline void ins(long long l, long long r, long long p, long long v, long long t,
                long long k) {
  if (l == r) {
    mn[k] = v;
    return;
  }
  pushdown(k);
  long long mid = l + r >> 1;
  if (p <= mid)
    ins(l, mid, p, v, t, k << 1);
  else
    ins(mid + 1, r, p, v, t, k << 1 | 1);
  pushup(k);
  return;
}
inline long long query(long long l, long long r, long long x, long long y,
                       long long t, long long k) {
  if (x <= l && r <= y) return sum[k];
  pushdown(k);
  long long mid = l + r >> 1, res = 0;
  if (x <= mid) res += query(l, mid, x, y, t, k << 1);
  if (y > mid) res += query(mid + 1, r, x, y, t, k << 1 | 1);
  return res;
}
int main() {
  N = read();
  for (long long i = 1; i <= N; i++) A[i] = read();
  Q = read();
  for (long long i = 1; i <= Q; i++) {
    long long l = read(), r = read();
    ques[r].push_back(make_pair(i, l));
  }
  build(1, N, 1);
  for (long long i = 1; i <= N; i++) {
    long long x = A[i], nl1 = i, nl2 = i;
    while (!smx.empty()) {
      if (smx.top().v < x) {
        long long l = smx.top().l, r = smx.top().r;
        add(1, N, l, r, x - smx.top().v, i, 1);
        nl1 = l, smx.pop();
      } else
        break;
    }
    while (!smn.empty()) {
      if (smn.top().v > x) {
        long long l = smn.top().l, r = smn.top().r;
        add(1, N, l, r, smn.top().v - x, i, 1);
        nl2 = l, smn.pop();
      } else
        break;
    }
    node tp1;
    tp1.v = x, tp1.l = nl1, tp1.r = i;
    node tp2;
    tp2.v = x, tp2.l = nl2, tp2.r = i;
    smx.push(tp1), smn.push(tp2);
    if (i - 1) add(1, N, 1, i - 1, -1, i, 1);
    ins(1, N, i, 0, i, 1);
    sum[1] += siz[1], nd[1] += 1;
    for (long long j = 0; j < ques[i].size(); j++) {
      long long l = ques[i][j].second, r = i, id = ques[i][j].first;
      ans[id] = query(1, N, l, r, i, 1);
    }
  }
  for (long long i = 1; i <= Q; i++) printf("%I64d\n", ans[i]);
  return 0;
}
