#include <bits/stdc++.h>
const int maxn = 1.2e5 + 5, Maxn = 2.4e5 + 5;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int n, m, p[maxn];
int Log[maxn], Max[maxn][18], Min[maxn][18];
void getM() {
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) Max[i][0] = Min[i][0] = p[i];
  for (int j = 1; j <= Log[n]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      Max[i][j] = max(Max[i][j - 1], Max[i + (1 << j - 1)][j - 1]),
      Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
}
int gMin(int l, int r) {
  int B = Log[r - l + 1];
  return min(Min[l][B], Min[r - (1 << B) + 1][B]);
}
int gMax(int l, int r) {
  int B = Log[r - l + 1];
  return max(Max[l][B], Max[r - (1 << B) + 1][B]);
}
bool legal(int l, int r) { return gMax(l, r) - gMin(l, r) - (r - l) == 0; }
int minn[maxn << 2], tag[maxn << 2];
void psp(int k) { minn[k] = min(minn[k << 1], minn[k << 1 | 1]); }
void gtg(int k, int v) { tag[k] += v, minn[k] += v; }
void psd(int k) {
  if (tag[k]) gtg(k << 1, tag[k]), gtg(k << 1 | 1, tag[k]), tag[k] = 0;
}
void bld(int k, int l, int r) {
  if (l == r) return minn[k] = l, void();
  int mid = l + r >> 1;
  bld(k << 1, l, mid), bld(k << 1 | 1, mid + 1, r), psp(k);
}
void mdf(int k, int l, int r, int x, int y, int v) {
  if (l > y || r < x) return;
  if (l >= x && r <= y) return gtg(k, v);
  int mid = l + r >> 1;
  psd(k), mdf(k << 1, l, mid, x, y, v), mdf(k << 1 | 1, mid + 1, r, x, y, v),
      psp(k);
}
int qry(int k, int l, int r) {
  if (l == r) return l;
  int mid = l + r >> 1;
  psd(k);
  return minn[k << 1] ? qry(k << 1 | 1, mid + 1, r) : qry(k << 1, l, mid);
}
struct Int {
  int l, r, v;
  Int(){};
  Int(int L, int R, int V) : l(L), r(R), v(V){};
} stmn[maxn], stmx[maxn];
int st[maxn], tp, tpmn, tpmx;
std ::vector<int> son[Maxn];
int nod, rt, id[maxn], L[Maxn], R[Maxn], Rl[Maxn], ty[Maxn];
void Build() {
  for (int i = 1; i <= n; ++i) {
    mdf(1, 1, n, 1, n, -1);
    while (tpmn && stmn[tpmn].v > p[i])
      mdf(1, 1, n, stmn[tpmn].l, stmn[tpmn].r, stmn[tpmn].v - p[i]), --tpmn;
    while (tpmx && stmx[tpmx].v < p[i])
      mdf(1, 1, n, stmx[tpmx].l, stmx[tpmx].r, p[i] - stmx[tpmx].v), --tpmx;
    ++tpmn, stmn[tpmn] = Int(stmn[tpmn - 1].r + 1, i, p[i]), ++tpmx,
            stmx[tpmx] = Int(stmx[tpmx - 1].r + 1, i, p[i]);
    ++nod, id[L[nod] = R[nod] = i] = nod;
    int now = nod, Lef = qry(1, 1, n);
    while (tp && L[st[tp]] >= Lef) {
      if (ty[st[tp]] && legal(Rl[st[tp]], i))
        son[st[tp]].push_back(now), R[st[tp]] = i, Rl[st[tp]] = L[now],
                                    now = st[tp--];
      else if (legal(L[st[tp]], i))
        ++nod, son[nod].push_back(st[tp]), son[nod].push_back(now),
            L[nod] = L[st[tp]], R[nod] = i, ty[nod] = 1, Rl[nod] = L[now],
            now = nod, --tp;
      else {
        ++nod, R[nod] = i, son[nod].push_back(now);
        do {
          L[nod] = L[st[tp]], son[nod].push_back(st[tp]);
        } while (!legal(L[st[tp--]], i));
        now = nod;
        std ::reverse(son[nod].begin(), son[nod].end());
      }
    }
    st[++tp] = now;
  }
  rt = st[1];
}
int dep[Maxn], pos[Maxn], fa[Maxn][18];
long long val[Maxn], sum[Maxn], pre[Maxn], suf[Maxn], jL[Maxn][18],
    jR[Maxn][18];
long long C2(int n) { return 1ll * n * (n - 1) / 2; }
void getS(int u) {
  val[u] = sum[u] = ty[u] ? C2(son[u].size()) : 1;
  for (int i = 0; i < son[u].size(); ++i)
    dep[son[u][i]] = dep[u] + 1, fa[son[u][i]][0] = u, getS(son[u][i]),
    sum[u] += sum[son[u][i]];
}
void getJ(int u) {
  int sons = son[u].size();
  for (int i = 1; i <= Log[dep[u]]; ++i)
    fa[u][i] = fa[fa[u][i - 1]][i - 1],
    jL[u][i] = jL[u][i - 1] + jL[fa[u][i - 1]][i - 1],
    jR[u][i] = jR[u][i - 1] + jR[fa[u][i - 1]][i - 1];
  if (!sons) return;
  for (int i = 0; i < sons; ++i) pos[son[u][i]] = i;
  pre[son[u][0]] = sum[son[u][0]];
  for (int i = 1; i < sons; ++i)
    pre[son[u][i]] = pre[son[u][i - 1]] + sum[son[u][i]];
  suf[son[u][sons - 1]] = sum[son[u][sons - 1]];
  for (int i = sons - 2; ~i; --i)
    suf[son[u][i]] = suf[son[u][i + 1]] + sum[son[u][i]];
  jR[son[u][0]][0] = 0;
  for (int i = 1; i < sons; ++i)
    jR[son[u][i]][0] =
        jR[son[u][i - 1]][0] + sum[son[u][i - 1]] + ty[u] * (i - 1);
  jL[son[u][sons - 1]][0] = 0;
  for (int i = sons - 2; ~i; --i)
    jL[son[u][i]][0] =
        jL[son[u][i + 1]][0] + sum[son[u][i + 1]] + ty[u] * (sons - i - 2);
  for (int i = 0; i < sons; ++i) getJ(son[u][i]);
}
struct pair {
  int x, y;
  pair(int X = 0, int Y = 0) : x(X), y(Y){};
};
pair LCA(int x, int y) {
  int Flag = dep[x] < dep[y];
  if (dep[x] < dep[y]) x ^= y ^= x ^= y;
  while (dep[x] ^ dep[y]) x = fa[x][Log[dep[x] - dep[y]]];
  for (int i = Log[dep[x]]; ~i; --i)
    if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
  return Flag ? pair(y, x) : pair(x, y);
}
long long getans(int l, int r) {
  if (l == r) return 1;
  long long ret = 0;
  int lp = id[l - 1], rp = id[r + 1];
  if (!lp && !rp)
    return sum[rt];
  else if (!lp) {
    for (int i = Log[dep[rp]]; ~i; --i)
      if (fa[rp][i] && (fa[rp][i] ^ rt)) ret += jR[rp][i], rp = fa[rp][i];
    ret += jR[rp][0];
  } else if (!rp) {
    for (int i = Log[dep[lp]]; ~i; --i)
      if (fa[lp][i] && (fa[lp][i] ^ rt)) ret += jL[lp][i], lp = fa[lp][i];
    ret += jL[lp][0];
  } else {
    pair pr = LCA(lp, rp);
    int lca = fa[pr.x][0];
    for (int i = Log[dep[lp]]; ~i; --i)
      if (dep[fa[lp][i]] >= dep[pr.x]) ret += jL[lp][i], lp = fa[lp][i];
    for (int i = Log[dep[rp]]; ~i; --i)
      if (dep[fa[rp][i]] >= dep[pr.y]) ret += jR[rp][i], rp = fa[rp][i];
    ret += (sum[lca] - val[lca] - pre[lp] - suf[rp]) +
           (ty[lca] ? C2(pos[pr.y] - pos[pr.x] - 1) : 0);
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
  getM(), bld(1, 1, n), Build(), getS(rt), getJ(rt), scanf("%d", &m);
  for (int i = 1, l, r; i <= m; ++i)
    scanf("%d %d", &l, &r), printf("%lld\n", getans(l, r));
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

A permutation p of length n is a sequence p_1, p_2, …, p_n consisting of n distinct integers, each of which from 1 to n (1 ≤ p_i ≤ n) .

Let's call the subsegment [l,r] of the permutation good if all numbers from the minimum on it to the maximum on this subsegment occur among the numbers p_l, p_{l+1}, ..., p_r.

For example, good segments of permutation [1, 3, 2, 5, 4] are:

  * [1, 1], 
  * [1, 3], 
  * [1, 5], 
  * [2, 2], 
  * [2, 3], 
  * [2, 5], 
  * [3, 3], 
  * [4, 4], 
  * [4, 5], 
  * [5, 5]. 



You are given a permutation p_1, p_2, …, p_n.

You need to answer q queries of the form: find the number of good subsegments of the given segment of permutation.

In other words, to answer one query, you need to calculate the number of good subsegments [x ... y] for some given segment [l ... r], such that l ≤ x ≤ y ≤ r.

Input

The first line contains a single integer n (1 ≤ n ≤ 120000) — the number of elements in the permutation.

The second line contains n distinct integers p_1, p_2, …, p_n separated by spaces (1 ≤ p_i ≤ n).

The third line contains an integer q (1 ≤ q ≤ 120000) — number of queries.

The following q lines describe queries, each line contains a pair of integers l, r separated by space (1 ≤ l ≤ r ≤ n).

Output

Print a q lines, i-th of them should contain a number of good subsegments of a segment, given in the i-th query.

Example

Input

5
1 3 2 5 4
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5


Output

1
2
5
6
10
1
3
4
7
1
2
4
1
3
1

### Response

```cpp
#include <bits/stdc++.h>
const int maxn = 1.2e5 + 5, Maxn = 2.4e5 + 5;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int n, m, p[maxn];
int Log[maxn], Max[maxn][18], Min[maxn][18];
void getM() {
  for (int i = 2; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) Max[i][0] = Min[i][0] = p[i];
  for (int j = 1; j <= Log[n]; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      Max[i][j] = max(Max[i][j - 1], Max[i + (1 << j - 1)][j - 1]),
      Min[i][j] = min(Min[i][j - 1], Min[i + (1 << j - 1)][j - 1]);
}
int gMin(int l, int r) {
  int B = Log[r - l + 1];
  return min(Min[l][B], Min[r - (1 << B) + 1][B]);
}
int gMax(int l, int r) {
  int B = Log[r - l + 1];
  return max(Max[l][B], Max[r - (1 << B) + 1][B]);
}
bool legal(int l, int r) { return gMax(l, r) - gMin(l, r) - (r - l) == 0; }
int minn[maxn << 2], tag[maxn << 2];
void psp(int k) { minn[k] = min(minn[k << 1], minn[k << 1 | 1]); }
void gtg(int k, int v) { tag[k] += v, minn[k] += v; }
void psd(int k) {
  if (tag[k]) gtg(k << 1, tag[k]), gtg(k << 1 | 1, tag[k]), tag[k] = 0;
}
void bld(int k, int l, int r) {
  if (l == r) return minn[k] = l, void();
  int mid = l + r >> 1;
  bld(k << 1, l, mid), bld(k << 1 | 1, mid + 1, r), psp(k);
}
void mdf(int k, int l, int r, int x, int y, int v) {
  if (l > y || r < x) return;
  if (l >= x && r <= y) return gtg(k, v);
  int mid = l + r >> 1;
  psd(k), mdf(k << 1, l, mid, x, y, v), mdf(k << 1 | 1, mid + 1, r, x, y, v),
      psp(k);
}
int qry(int k, int l, int r) {
  if (l == r) return l;
  int mid = l + r >> 1;
  psd(k);
  return minn[k << 1] ? qry(k << 1 | 1, mid + 1, r) : qry(k << 1, l, mid);
}
struct Int {
  int l, r, v;
  Int(){};
  Int(int L, int R, int V) : l(L), r(R), v(V){};
} stmn[maxn], stmx[maxn];
int st[maxn], tp, tpmn, tpmx;
std ::vector<int> son[Maxn];
int nod, rt, id[maxn], L[Maxn], R[Maxn], Rl[Maxn], ty[Maxn];
void Build() {
  for (int i = 1; i <= n; ++i) {
    mdf(1, 1, n, 1, n, -1);
    while (tpmn && stmn[tpmn].v > p[i])
      mdf(1, 1, n, stmn[tpmn].l, stmn[tpmn].r, stmn[tpmn].v - p[i]), --tpmn;
    while (tpmx && stmx[tpmx].v < p[i])
      mdf(1, 1, n, stmx[tpmx].l, stmx[tpmx].r, p[i] - stmx[tpmx].v), --tpmx;
    ++tpmn, stmn[tpmn] = Int(stmn[tpmn - 1].r + 1, i, p[i]), ++tpmx,
            stmx[tpmx] = Int(stmx[tpmx - 1].r + 1, i, p[i]);
    ++nod, id[L[nod] = R[nod] = i] = nod;
    int now = nod, Lef = qry(1, 1, n);
    while (tp && L[st[tp]] >= Lef) {
      if (ty[st[tp]] && legal(Rl[st[tp]], i))
        son[st[tp]].push_back(now), R[st[tp]] = i, Rl[st[tp]] = L[now],
                                    now = st[tp--];
      else if (legal(L[st[tp]], i))
        ++nod, son[nod].push_back(st[tp]), son[nod].push_back(now),
            L[nod] = L[st[tp]], R[nod] = i, ty[nod] = 1, Rl[nod] = L[now],
            now = nod, --tp;
      else {
        ++nod, R[nod] = i, son[nod].push_back(now);
        do {
          L[nod] = L[st[tp]], son[nod].push_back(st[tp]);
        } while (!legal(L[st[tp--]], i));
        now = nod;
        std ::reverse(son[nod].begin(), son[nod].end());
      }
    }
    st[++tp] = now;
  }
  rt = st[1];
}
int dep[Maxn], pos[Maxn], fa[Maxn][18];
long long val[Maxn], sum[Maxn], pre[Maxn], suf[Maxn], jL[Maxn][18],
    jR[Maxn][18];
long long C2(int n) { return 1ll * n * (n - 1) / 2; }
void getS(int u) {
  val[u] = sum[u] = ty[u] ? C2(son[u].size()) : 1;
  for (int i = 0; i < son[u].size(); ++i)
    dep[son[u][i]] = dep[u] + 1, fa[son[u][i]][0] = u, getS(son[u][i]),
    sum[u] += sum[son[u][i]];
}
void getJ(int u) {
  int sons = son[u].size();
  for (int i = 1; i <= Log[dep[u]]; ++i)
    fa[u][i] = fa[fa[u][i - 1]][i - 1],
    jL[u][i] = jL[u][i - 1] + jL[fa[u][i - 1]][i - 1],
    jR[u][i] = jR[u][i - 1] + jR[fa[u][i - 1]][i - 1];
  if (!sons) return;
  for (int i = 0; i < sons; ++i) pos[son[u][i]] = i;
  pre[son[u][0]] = sum[son[u][0]];
  for (int i = 1; i < sons; ++i)
    pre[son[u][i]] = pre[son[u][i - 1]] + sum[son[u][i]];
  suf[son[u][sons - 1]] = sum[son[u][sons - 1]];
  for (int i = sons - 2; ~i; --i)
    suf[son[u][i]] = suf[son[u][i + 1]] + sum[son[u][i]];
  jR[son[u][0]][0] = 0;
  for (int i = 1; i < sons; ++i)
    jR[son[u][i]][0] =
        jR[son[u][i - 1]][0] + sum[son[u][i - 1]] + ty[u] * (i - 1);
  jL[son[u][sons - 1]][0] = 0;
  for (int i = sons - 2; ~i; --i)
    jL[son[u][i]][0] =
        jL[son[u][i + 1]][0] + sum[son[u][i + 1]] + ty[u] * (sons - i - 2);
  for (int i = 0; i < sons; ++i) getJ(son[u][i]);
}
struct pair {
  int x, y;
  pair(int X = 0, int Y = 0) : x(X), y(Y){};
};
pair LCA(int x, int y) {
  int Flag = dep[x] < dep[y];
  if (dep[x] < dep[y]) x ^= y ^= x ^= y;
  while (dep[x] ^ dep[y]) x = fa[x][Log[dep[x] - dep[y]]];
  for (int i = Log[dep[x]]; ~i; --i)
    if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
  return Flag ? pair(y, x) : pair(x, y);
}
long long getans(int l, int r) {
  if (l == r) return 1;
  long long ret = 0;
  int lp = id[l - 1], rp = id[r + 1];
  if (!lp && !rp)
    return sum[rt];
  else if (!lp) {
    for (int i = Log[dep[rp]]; ~i; --i)
      if (fa[rp][i] && (fa[rp][i] ^ rt)) ret += jR[rp][i], rp = fa[rp][i];
    ret += jR[rp][0];
  } else if (!rp) {
    for (int i = Log[dep[lp]]; ~i; --i)
      if (fa[lp][i] && (fa[lp][i] ^ rt)) ret += jL[lp][i], lp = fa[lp][i];
    ret += jL[lp][0];
  } else {
    pair pr = LCA(lp, rp);
    int lca = fa[pr.x][0];
    for (int i = Log[dep[lp]]; ~i; --i)
      if (dep[fa[lp][i]] >= dep[pr.x]) ret += jL[lp][i], lp = fa[lp][i];
    for (int i = Log[dep[rp]]; ~i; --i)
      if (dep[fa[rp][i]] >= dep[pr.y]) ret += jR[rp][i], rp = fa[rp][i];
    ret += (sum[lca] - val[lca] - pre[lp] - suf[rp]) +
           (ty[lca] ? C2(pos[pr.y] - pos[pr.x] - 1) : 0);
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
  getM(), bld(1, 1, n), Build(), getS(rt), getJ(rt), scanf("%d", &m);
  for (int i = 1, l, r; i <= m; ++i)
    scanf("%d %d", &l, &r), printf("%lld\n", getans(l, r));
  return 0;
}

```