#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2e4 + 10;
struct Queries {
  int l, r, id;
  bool operator<(const Queries &b) const { return r < b.r; }
} q[N];
struct Node {
  int val, tag, tim, num;
  long long ans;
} T[N << 2];
void Build(int o, int l, int r) {
  T[o].val = l - 1;
  T[o].num = 1;
  if (l == r) return;
  int mid = l + r >> 1;
  Build(o << 1, l, mid);
  Build(o << 1 | 1, mid + 1, r);
}
void AddVal(int x, int v) {
  T[x].val += v;
  T[x].tag += v;
}
void AddTim(int x, int v) {
  T[x].tim += v;
  T[x].ans += 1LL * v * T[x].num;
}
void Down(int o) {
  int ls = o << 1, rs = o << 1 | 1;
  if (T[o].tag) {
    AddVal(ls, T[o].tag);
    AddVal(rs, T[o].tag);
    T[o].tag = 0;
  }
  if (T[o].tim) {
    if (T[o].val == T[ls].val) AddTim(ls, T[o].tim);
    if (T[o].val == T[rs].val) AddTim(rs, T[o].tim);
    T[o].tim = 0;
  }
}
void Up(int o) {
  int ls = o << 1, rs = o << 1 | 1;
  T[o].val = min(T[ls].val, T[rs].val);
  T[o].ans = T[ls].ans + T[rs].ans;
  T[o].num = 0;
  if (T[o].val == T[ls].val) T[o].num += T[ls].num;
  if (T[o].val == T[rs].val) T[o].num += T[rs].num;
}
void Modify(int o, int l, int r, int x, int y, int v) {
  if (x <= l && r <= y) {
    AddVal(o, v);
    return;
  }
  int mid = l + r >> 1;
  Down(o);
  if (x <= mid) Modify(o << 1, l, mid, x, y, v);
  if (mid < y) Modify(o << 1 | 1, mid + 1, r, x, y, v);
  Up(o);
}
long long Query(int o, int l, int r, int x, int y) {
  if (x <= l && r <= y) return T[o].ans;
  int mid = l + r >> 1;
  long long out = 0;
  Down(o);
  if (x <= mid) out += Query(o << 1, l, mid, x, y);
  if (mid < y) out += Query(o << 1 | 1, mid + 1, r, x, y);
  return out;
}
int n, a[N], Q, topx, topi, X[N], I[N];
long long ans[N];
int main(void) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &Q);
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + Q + 1);
  Build(1, 1, n);
  for (int i = 1, j = 1; i <= n && j <= Q; i++) {
    AddVal(1, -1);
    while (topx && a[X[topx]] < a[i])
      Modify(1, 1, n, X[topx - 1] + 1, X[topx], a[i] - a[X[topx]]), topx--;
    while (topi && a[I[topi]] > a[i])
      Modify(1, 1, n, I[topi - 1] + 1, I[topi], a[I[topi]] - a[i]), topi--;
    X[++topx] = I[++topi] = i;
    AddTim(1, 1);
    while (j <= Q && q[j].r == i)
      ans[q[j].id] = Query(1, 1, n, q[j].l, q[j].r), j++;
  }
  for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
  return 0;
}
