#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
const int N = 400005;
int n, a[N];
vector<int> adj[N];
namespace DisjunctionTree {
int lg[N], mx[N][22], mi[N][22];
int queryMx(int L, int R) {
int k = lg[R - L + 1];
return max(mx[L][k], mx[R - (1 << k) + 1][k]);
}
int queryMi(int L, int R) {
int k = lg[R - L + 1];
return min(mi[L][k], mi[R - (1 << k) + 1][k]);
}
bool judge(int L, int R) {
return queryMx(L, R) - queryMi(L, R) == R - L;
}
int lazy[N << 2], mn[N << 2];
void pushup(int p) {
mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}
void pushtag(int p, int tag) {
mn[p] += tag;
lazy[p] += tag;
}
void pushdown(int p) {
if (lazy[p]) {
pushtag(p << 1, lazy[p]);
pushtag(p << 1 | 1, lazy[p]);
lazy[p] = 0;
}
}
void modify(int p, int L, int R, int QL, int QR, int k) {
if (QL <= L && R <= QR) {
pushtag(p, k);
return;
}
pushdown(p);
int mid = L + R >> 1;
if (QR <= mid) modify(p << 1, L, mid, QL, QR, k);
else if (QL >= mid + 1) modify(p << 1 | 1, mid + 1, R, QL, QR, k);
else {
modify(p << 1, L, mid, QL, QR, k);
modify(p << 1 | 1, mid + 1, R, QL, QR, k);
}
pushup(p);
}
int query(int p, int L, int R) {
if (L == R) return L;
pushdown(p);
int mid = L + R >> 1;
if (mn[p << 1] == 0) return query(p << 1, L, mid);
return query(p << 1 | 1, mid + 1, R);
}
int st1[N], tp1, st2[N], tp2, st3[N << 1], tp3;
int cnt, L[N << 1], R[N << 1], M[N << 1], typ[N << 1];
// typ = 1 代表 合点
// typ = 0 代表 析点
long long w[N << 1], pre[N << 1], suf[N << 1], siz[N << 1], sum[N << 1];
int fa[N << 1][22], deep[N << 1], idx[N << 1], rk[N << 1];
long long Cn2(long long n) {
return n * (n - 1) / 2;
}
void dfs1(int u, int p) {
fa[u][0] = p;
deep[u] = deep[p] + 1;
siz[u] = (typ[u] == 1 ? Cn2(adj[u].size()) : 1);
for (int i = 1 ; i <= 21 ; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
long long temp = 0;
for (int i = 0 ; i < (int)adj[u].size() ; i++) {
int to = adj[u][i];
dfs1(to, u);
siz[u] += siz[to];
pre[to] = temp + (typ[u] == 1 ? Cn2(i) : 0);
temp += siz[to];
sum[to] = temp;
rk[to] = i + 1;
}
temp = 0;
for (int i = (int)adj[u].size() - 1 ; i >= 0 ; i--) {
int to = adj[u][i];
suf[to] = temp + (typ[u] == 1 ? Cn2((int)adj[u].size() - 1 - i) : 0);
temp += siz[to];
}
}
void dfs2(int u, int p) {
pre[u] += pre[p];
suf[u] += suf[p];
for (auto &to : adj[u]) {
dfs2(to, u);
}
}
int jump(int x, int y) {
for (int i = 21 ; i >= 0 ; i--) {
if (deep[fa[x][i]] <= deep[y]) continue;
x = fa[x][i];
}
return x;
}
int LCA(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 21 ; i >= 0 ; i--) {
if (deep[fa[x][i]] < deep[y]) continue;
x = fa[x][i];
}
if (x == y) return x;
for (int i = 21 ; i >= 0 ; i--) {
if (fa[x][i] == fa[y][i]) continue;
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
int rt;
long long query(int L, int R) {
L--;
R++;
int z = LCA(idx[L], idx[R]);
int x = jump(idx[L], z), y = jump(idx[R], z);
long long res = (pre[idx[R]] - pre[y]) + (suf[idx[L]] - suf[x]) + sum[y] - sum[x] - siz[y] + (typ[z] == 1 ? Cn2(rk[y] - rk[x] - 1) : 0);
return res;
}
long long queryPre(int R) {
R++;
int x = jump(idx[R], rt);
long long res = (pre[idx[R]] - pre[x]) + (sum[x] - siz[x]) + (typ[rt] == 1 ? Cn2(rk[x] - 1) : 0);
return res;
}
long long querySuf(int L) {
L--;
int x = jump(idx[L], rt);
long long res = (suf[idx[L]] - suf[x]) + (sum[adj[rt].back()] - sum[x]) + (typ[rt] == 1 ? Cn2((int)adj[rt].size() - rk[x]) : 0);
return res;
}
void build() {
for (int i = 2 ; i <= n ; i++) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1 ; i <= n ; ++i) {
mx[i][0] = mi[i][0] = a[i];
}
for (int j = 1 ; j <= lg[n] ; j++) {
for (int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << j - 1)][j - 1]);
}
}
for (int i = 1 ; i <= n ; i++) {
while (tp1 && a[st1[tp1]] < a[i]) {
modify(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], -a[st1[tp1]]);
tp1--;
}
while (tp2 && a[st2[tp2]] > a[i]) {
modify(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], a[st2[tp2]]);
tp2--;
}
modify(1, 1, n, st1[tp1] + 1, i, a[i]);
st1[++tp1] = i;
modify(1, 1, n, st2[tp2] + 1, i, -a[i]);
st2[++tp2] = i;
idx[i] = ++cnt;
int le = query(1, 1, n), now = cnt;
L[now] = R[now] = i;
while (tp3 && L[st3[tp3]] >= le) {
int k = st3[tp3];
if (typ[k] && judge(M[k], i)) {
R[k] = i;
adj[k].push_back(now);
now = k;
} else if (judge(L[k], i)) {
typ[++cnt] = 1;
L[cnt] = L[k];
R[cnt] = i;
M[cnt] = L[now];
adj[cnt].push_back(k);
adj[cnt].push_back(now);
now = cnt;
} else {
cnt++;
adj[cnt].push_back(now);
do {
adj[cnt].push_back(st3[tp3]);
tp3--;
} while(tp3 && !judge(L[st3[tp3]], i));
L[cnt] = L[st3[tp3]];
R[cnt] = i;
adj[cnt].push_back(st3[tp3]);
now = cnt;
}
tp3--;
}
st3[++tp3] = now;
modify(1, 1, n, 1, i, -1);
}
rt = st3[tp3];
for (int i = 1 ; i <= cnt ; i++) {
sort(begin(adj[i]), end(adj[i]), [&](const auto &x, const auto &y){
return L[x] < L[y];
});
}
dfs1(rt, 0);
dfs2(rt, 0);
}
}; // DisjunctionTree
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
using DisjunctionTree::rt;
using DisjunctionTree::siz;
using DisjunctionTree::build;
using DisjunctionTree::querySuf;
using DisjunctionTree::queryPre;
using DisjunctionTree::query;
build();
int q;
cin >> q;
while (q--) {
int L, R;
cin >> L >> R;
if (L == 1 && R == n) {
cout << siz[rt] << "\n";
} else if (L == 1 && R != n) {
cout << queryPre(R) << "\n";
} else if (L != 1 && R == n) {
cout << querySuf(L) << "\n";
} else {
cout << query(L, R) << "\n";
}
}
return 0;
}