#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char ch = getchar();
  long long s = 0, w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * w;
}
long long ans[120010 << 2];
long long minn[120010 << 2], sum[120010 << 2];
long long tag1[120010 << 2], tag2[120010 << 2];
long long n, m, a[120010];
struct node {
  long long l, r, id;
} q[120010];
long long answer[120010];
inline long long cmp(node a, node b) { return a.r < b.r; }
long long st1[120010], st2[120010], top1, top2;
inline void addmin(long long x, long long v) {
  minn[x] += v;
  tag1[x] += v;
}
inline void addans(long long x, long long v) {
  ans[x] += 1LL * v * sum[x];
  tag2[x] += v;
}
inline void pushdown(long long x) {
  if (tag1[x]) {
    addmin(x << 1, tag1[x]);
    addmin(x << 1 | 1, tag1[x]);
    tag1[x] = 0;
  }
  if (tag2[x]) {
    if (minn[x << 1] == minn[x]) addans(x << 1, tag2[x]);
    if (minn[x << 1 | 1] == minn[x]) addans(x << 1 | 1, tag2[x]);
    tag2[x] = 0;
  }
}
inline void pushup(long long x) {
  minn[x] = min(minn[x << 1], minn[x << 1 | 1]);
  if (minn[x << 1] < minn[x << 1 | 1])
    sum[x] = sum[x << 1];
  else if (minn[x << 1 | 1] < minn[x << 1])
    sum[x] = sum[x << 1 | 1];
  else
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
void build(long long l, long long r, long long x) {
  if (l == r) {
    sum[x] = 1;
    minn[x] = l;
    return;
  }
  long long mid = (l + r) >> 1;
  build(l, mid, x << 1);
  build(mid + 1, r, x << 1 | 1);
  pushup(x);
}
void update(long long left, long long right, long long l, long long r,
            long long x, long long v) {
  if (left == l && right == r) {
    addmin(x, v);
    return;
  }
  long long mid = (l + r) >> 1;
  pushdown(x);
  if (right <= mid)
    update(left, right, l, mid, x << 1, v);
  else if (left > mid)
    update(left, right, mid + 1, r, x << 1 | 1, v);
  else
    update(left, mid, l, mid, x << 1, v),
        update(mid + 1, right, mid + 1, r, x << 1 | 1, v);
  pushup(x);
}
long long query(long long left, long long right, long long l, long long r,
                long long x) {
  if (left == l && right == r) {
    return ans[x];
  }
  pushdown(x);
  long long mid = (l + r) >> 1;
  if (right <= mid)
    return query(left, right, l, mid, x << 1);
  else if (left > mid)
    return query(left, right, mid + 1, r, x << 1 | 1);
  else
    return query(left, mid, l, mid, x << 1) +
           query(mid + 1, right, mid + 1, r, x << 1 | 1);
}
int main() {
  n = read();
  for (register long long i = 1; i <= n; i++) a[i] = read();
  m = read();
  for (register long long i = 1; i <= m; i++)
    q[i].l = read(), q[i].r = read(), q[i].id = i;
  sort(q + 1, q + m + 1, cmp);
  build(1, n, 1);
  long long pos = 1;
  for (register long long i = 1; i <= n; i++) {
    addmin(1, -1);
    while (top1 && a[i] > a[st1[top1]]) {
      update(st1[top1 - 1] + 1, st1[top1], 1, n, 1, -a[st1[top1]]);
      top1--;
    }
    while (top2 && a[i] < a[st2[top2]]) {
      update(st2[top2 - 1] + 1, st2[top2], 1, n, 1, a[st2[top2]]);
      top2--;
    }
    update(st1[top1] + 1, i, 1, n, 1, a[i]);
    st1[++top1] = i;
    update(st2[top2] + 1, i, 1, n, 1, -a[i]);
    st2[++top2] = i;
    addans(1, 1);
    while (q[pos].r == i && pos <= m) {
      answer[q[pos].id] = query(q[pos].l, q[pos].r, 1, n, 1);
      pos++;
    }
  }
  for (register long long i = 1; i <= m; i++) printf("%lld\n", answer[i]);
  return 0;
}
