#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const int N = 123456;
struct node {
  int mn, mcnt, mf, fg;
  long long s;
} nd[N * 4];
int n, q, l, r, p[N];
long long ans[N];
vector<pair<int, int>> qr[N];
stack<pair<pair<int, int>, int>> s1, s2;
void build(int p, int l, int r) {
  nd[p].mn = l;
  nd[p].mcnt = 1;
  int md = (l + r) >> 1;
  if (l != r) {
    build(p + p, l, md);
    build(p + p + 1, md + 1, r);
  }
}
void setf1(int p, int fg) {
  nd[p].fg += fg;
  nd[p].mn += fg;
}
void setf2(int p, long long fg) {
  nd[p].mf += fg;
  nd[p].s += nd[p].mcnt * fg;
}
void push(int p) {
  if (nd[p].fg) {
    setf1(p + p, nd[p].fg);
    setf1(p + p + 1, nd[p].fg);
    nd[p].fg = 0;
  }
  if (nd[p].mf) {
    if (nd[p].mn == nd[p + p].mn) setf2(p + p, nd[p].mf);
    if (nd[p].mn == nd[p + p + 1].mn) setf2(p + p + 1, nd[p].mf);
    nd[p].mf = 0;
  }
}
void upd(int p) {
  nd[p].mn = min(nd[p + p].mn, nd[p + p + 1].mn);
  nd[p].mcnt = 0;
  if (nd[p].mn == nd[p + p].mn) nd[p].mcnt += nd[p + p].mcnt;
  if (nd[p].mn == nd[p + p + 1].mn) nd[p].mcnt += nd[p + p + 1].mcnt;
  nd[p].s = nd[p + p].s + nd[p + p + 1].s;
}
void modify(int p, int l, int r, int tl, int tr, int v) {
  if (l == tl && r == tr)
    setf1(p, v);
  else {
    push(p);
    int md = (l + r) >> 1;
    if (tr <= md)
      modify(p + p, l, md, tl, tr, v);
    else if (tl > md)
      modify(p + p + 1, md + 1, r, tl, tr, v);
    else
      modify(p + p, l, md, tl, md, v),
          modify(p + p + 1, md + 1, r, md + 1, tr, v);
    upd(p);
  }
}
long long query(int p, int l, int r, int tl, int tr) {
  if (l == tl && r == tr)
    return nd[p].s;
  else {
    push(p);
    int md = (l + r) >> 1;
    if (tr <= md)
      return query(p + p, l, md, tl, tr);
    else if (tl > md)
      return query(p + p + 1, md + 1, r, tl, tr);
    else
      return query(p + p, l, md, tl, md) +
             query(p + p + 1, md + 1, r, md + 1, tr);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n + 1; i++) scanf("%d", p + i);
  build(1, 1, n);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &l, &r);
    qr[r].push_back(make_pair(l, i));
  }
  for (int i = 1; i < n + 1; i++) {
    modify(1, 1, n, 1, n, -1);
    int pl = i;
    while (!s1.empty()) {
      if (s1.top().second > p[i]) {
        modify(1, 1, n, s1.top().first.first, s1.top().first.second,
               s1.top().second);
        pl = s1.top().first.first;
        s1.pop();
      } else
        break;
    }
    int ql = i;
    while (!s2.empty()) {
      if (s2.top().second < p[i]) {
        modify(1, 1, n, s2.top().first.first, s2.top().first.second,
               -s2.top().second);
        ql = s2.top().first.first;
        s2.pop();
      } else
        break;
    }
    s1.push(make_pair(make_pair(pl, i), p[i]));
    s2.push(make_pair(make_pair(ql, i), p[i]));
    modify(1, 1, n, pl, i, -p[i]);
    modify(1, 1, n, ql, i, p[i]);
    setf2(1, 1);
    for (auto p : qr[i]) ans[p.second] = query(1, 1, n, p.first, i);
  }
  for (int i = 0; i < q; i++) printf("%lld\n", ans[i]);
}
