#include <bits/stdc++.h>
const int MAXN = 1.2e5 + 10;
int n, Q, cnt, rt, dfnc;
int a[MAXN], st1[MAXN], st2[MAXN], st[MAXN], id[MAXN], L[MAXN * 2], R[MAXN * 2],
    q[MAXN * 2];
int dfn[MAXN * 2], sz[MAXN * 2], son[MAXN * 2], top[MAXN * 2], fa[MAXN * 2],
    dep[MAXN * 2], rid[MAXN * 2], sc[MAXN * 2];
long long pre[MAXN * 2], suf[MAXN * 2], sum[MAXN * 2], sumS[MAXN * 2];
bool type[MAXN * 2];
std::vector<int> E[MAXN * 2];
template <int N>
struct RMQ {
  int lg[N], ST0[19][N], ST1[19][N];
  inline int min(int x, int y) { return a[x] < a[y] ? x : y; }
  inline int max(int x, int y) { return a[x] > a[y] ? x : y; }
  inline void init() {
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) ST0[0][i] = ST1[0][i] = i;
    for (int i = 1; (1 << i) <= n; ++i)
      for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        ST0[i][j] = min(ST0[i - 1][j], ST0[i - 1][j + (1 << (i - 1))]),
        ST1[i][j] = max(ST1[i - 1][j], ST1[i - 1][j + (1 << (i - 1))]);
  }
  inline int queryMin(int L, int R) {
    int k = lg[R - L + 1];
    return a[min(ST0[k][L], ST0[k][R - (1 << k) + 1])];
  }
  inline int queryMax(int L, int R) {
    int k = lg[R - L + 1];
    return a[max(ST1[k][L], ST1[k][R - (1 << k) + 1])];
  }
};
RMQ<MAXN> rqy;
inline int min(int L, int R) { return rqy.queryMin(L, R); }
inline int max(int L, int R) { return rqy.queryMax(L, R); }
template <int N>
struct SegmentTree {
  static const int M = N << 2;
  int tag[M], min[M];
  inline void modify(int x, int val) { tag[x] += val, min[x] += val; }
  inline void pushUp(int x) {
    min[x] = std::min(min[((x) << 1)], min[((x) << 1 | 1)]);
  }
  inline void pushDown(int x) {
    if (tag[x])
      modify(((x) << 1), tag[x]), modify(((x) << 1 | 1), tag[x]), tag[x] = 0;
  }
  void update(int x, int L, int R, int ql, int qr, int val) {
    if (ql <= L && R <= qr) return modify(x, val);
    int mid = (L + R) >> 1;
    pushDown(x);
    if (ql <= mid) update(((x) << 1), L, mid, ql, qr, val);
    if (qr > mid) update(((x) << 1 | 1), mid + 1, R, ql, qr, val);
    pushUp(x);
  }
  int query(int x, int L, int R) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    pushDown(x);
    if (!min[((x) << 1)]) return query(((x) << 1), L, mid);
    return query(((x) << 1 | 1), mid + 1, R);
  }
};
SegmentTree<MAXN> Tr;
inline bool isCon(int L, int R) { return max(L, R) - min(L, R) == R - L; }
inline void buildACTree() {
  int top = 0, top1 = 0, top2 = 0;
  for (int i = 1; i <= n; ++i) {
    while (top1 && a[i] > a[st1[top1]])
      Tr.update(1, 1, n, st1[top1 - 1] + 1, st1[top1], -a[st1[top1]]), --top1;
    while (top2 && a[i] < a[st2[top2]])
      Tr.update(1, 1, n, st2[top2 - 1] + 1, st2[top2], a[st2[top2]]), --top2;
    Tr.update(1, 1, n, st1[top1] + 1, i, a[i]), st1[++top1] = i;
    Tr.update(1, 1, n, st2[top2] + 1, i, -a[i]), st2[++top2] = i;
    id[i] = ++cnt, L[cnt] = R[cnt] = i;
    int cur = cnt, exL = Tr.query(1, 1, n);
    while (top && L[st[top]] >= exL) {
      if (type[st[top]] && isCon(q[st[top]], i))
        R[st[top]] = i, fa[cur] = st[top], cur = st[top--];
      else if (isCon(L[st[top]], i)) {
        type[++cnt] = true, L[cnt] = L[st[top]], R[cnt] = i, q[cnt] = L[cur];
        fa[st[top--]] = fa[cur] = cnt, cur = cnt;
      } else {
        fa[cur] = ++cnt;
        while (top && !isCon(L[st[top]], i)) fa[st[top--]] = cnt;
        L[cnt] = L[st[top]], R[cnt] = i, fa[st[top--]] = cnt, cur = cnt;
      }
    }
    st[++top] = cur;
    Tr.update(1, 1, n, 1, i, -1);
  }
  rt = st[1];
}
void dfs1(int u) {
  sz[u] = 1;
  if (type[u])
    sum[u] = 1LL * ((int)E[u].size()) * ((int)E[u].size() - 1) / 2;
  else
    sum[u] = 1;
  for (const auto &v : E[u]) {
    dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v], sum[u] += sum[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
  if (L[u] == R[u]) return;
  int sz = E[u].size();
  sumS[E[u][0]] = sum[E[u][0]];
  for (int i = 1; i < sz; ++i)
    pre[E[u][i]] = pre[E[u][i - 1]] + sum[E[u][i - 1]] + (type[u] ? i - 1 : 0),
    sc[E[u][i]] = i, sumS[E[u][i]] = sumS[E[u][i - 1]] + sum[E[u][i]];
  for (int i = sz - 2; ~i; --i)
    suf[E[u][i]] =
        suf[E[u][i + 1]] + sum[E[u][i + 1]] + (type[u] ? sz - i - 2 : 0);
}
void dfs2(int u, int tp) {
  top[u] = tp, dfn[u] = ++dfnc, rid[dfnc] = u;
  if (son[u]) pre[son[u]] += pre[u], suf[son[u]] += suf[u], dfs2(son[u], tp);
  for (const auto &v : E[u])
    if (v != son[u]) pre[v] += pre[u], suf[v] += suf[u], dfs2(v, v);
}
inline int LCA(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    u = fa[top[u]];
  }
  return dep[u] < dep[v] ? u : v;
}
inline int Kth(int u, int K) {
  while (K >= dep[u] - dep[top[u]] + 1)
    K -= dep[u] - dep[top[u]] + 1, u = fa[top[u]];
  return rid[dfn[u] - K];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  rqy.init(), buildACTree();
  for (int i = 1; i <= cnt; ++i)
    if (fa[i]) E[fa[i]].emplace_back(i);
  dep[rt] = 1, dfs1(rt), dfs2(rt, rt);
  scanf("%d", &Q);
  for (int i = 1, L, R; i <= Q; ++i) {
    scanf("%d%d", &L, &R), --L, ++R;
    int x = id[L], y = id[R];
    if (!L && R > n) {
      printf("%lld\n", sum[rt]);
      continue;
    }
    if (!L) {
      int lca = rt, yk = Kth(y, dep[y] - dep[lca] - 1), t = sc[yk];
      printf("%lld\n", (pre[y] - pre[yk]) + (sumS[yk] - sum[yk]) +
                           (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
      continue;
    }
    if (R > n) {
      int lca = rt, xk = Kth(x, dep[x] - dep[lca] - 1),
          t = (int)E[lca].size() - sc[xk] - 1;
      printf("%lld\n", (suf[x] - suf[xk]) + (sumS[E[lca].back()] - sumS[xk]) +
                           (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
      continue;
    }
    int lca = LCA(x, y), xk = Kth(x, dep[x] - dep[lca] - 1),
        yk = Kth(y, dep[y] - dep[lca] - 1), t = sc[yk] - sc[xk] - 1;
    printf("%lld\n", (suf[x] - suf[xk]) + (pre[y] - pre[yk]) +
                         (sumS[yk] - sumS[xk] - sum[yk]) +
                         (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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 + 10;
int n, Q, cnt, rt, dfnc;
int a[MAXN], st1[MAXN], st2[MAXN], st[MAXN], id[MAXN], L[MAXN * 2], R[MAXN * 2],
    q[MAXN * 2];
int dfn[MAXN * 2], sz[MAXN * 2], son[MAXN * 2], top[MAXN * 2], fa[MAXN * 2],
    dep[MAXN * 2], rid[MAXN * 2], sc[MAXN * 2];
long long pre[MAXN * 2], suf[MAXN * 2], sum[MAXN * 2], sumS[MAXN * 2];
bool type[MAXN * 2];
std::vector<int> E[MAXN * 2];
template <int N>
struct RMQ {
  int lg[N], ST0[19][N], ST1[19][N];
  inline int min(int x, int y) { return a[x] < a[y] ? x : y; }
  inline int max(int x, int y) { return a[x] > a[y] ? x : y; }
  inline void init() {
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) ST0[0][i] = ST1[0][i] = i;
    for (int i = 1; (1 << i) <= n; ++i)
      for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        ST0[i][j] = min(ST0[i - 1][j], ST0[i - 1][j + (1 << (i - 1))]),
        ST1[i][j] = max(ST1[i - 1][j], ST1[i - 1][j + (1 << (i - 1))]);
  }
  inline int queryMin(int L, int R) {
    int k = lg[R - L + 1];
    return a[min(ST0[k][L], ST0[k][R - (1 << k) + 1])];
  }
  inline int queryMax(int L, int R) {
    int k = lg[R - L + 1];
    return a[max(ST1[k][L], ST1[k][R - (1 << k) + 1])];
  }
};
RMQ<MAXN> rqy;
inline int min(int L, int R) { return rqy.queryMin(L, R); }
inline int max(int L, int R) { return rqy.queryMax(L, R); }
template <int N>
struct SegmentTree {
  static const int M = N << 2;
  int tag[M], min[M];
  inline void modify(int x, int val) { tag[x] += val, min[x] += val; }
  inline void pushUp(int x) {
    min[x] = std::min(min[((x) << 1)], min[((x) << 1 | 1)]);
  }
  inline void pushDown(int x) {
    if (tag[x])
      modify(((x) << 1), tag[x]), modify(((x) << 1 | 1), tag[x]), tag[x] = 0;
  }
  void update(int x, int L, int R, int ql, int qr, int val) {
    if (ql <= L && R <= qr) return modify(x, val);
    int mid = (L + R) >> 1;
    pushDown(x);
    if (ql <= mid) update(((x) << 1), L, mid, ql, qr, val);
    if (qr > mid) update(((x) << 1 | 1), mid + 1, R, ql, qr, val);
    pushUp(x);
  }
  int query(int x, int L, int R) {
    if (L == R) return L;
    int mid = (L + R) >> 1;
    pushDown(x);
    if (!min[((x) << 1)]) return query(((x) << 1), L, mid);
    return query(((x) << 1 | 1), mid + 1, R);
  }
};
SegmentTree<MAXN> Tr;
inline bool isCon(int L, int R) { return max(L, R) - min(L, R) == R - L; }
inline void buildACTree() {
  int top = 0, top1 = 0, top2 = 0;
  for (int i = 1; i <= n; ++i) {
    while (top1 && a[i] > a[st1[top1]])
      Tr.update(1, 1, n, st1[top1 - 1] + 1, st1[top1], -a[st1[top1]]), --top1;
    while (top2 && a[i] < a[st2[top2]])
      Tr.update(1, 1, n, st2[top2 - 1] + 1, st2[top2], a[st2[top2]]), --top2;
    Tr.update(1, 1, n, st1[top1] + 1, i, a[i]), st1[++top1] = i;
    Tr.update(1, 1, n, st2[top2] + 1, i, -a[i]), st2[++top2] = i;
    id[i] = ++cnt, L[cnt] = R[cnt] = i;
    int cur = cnt, exL = Tr.query(1, 1, n);
    while (top && L[st[top]] >= exL) {
      if (type[st[top]] && isCon(q[st[top]], i))
        R[st[top]] = i, fa[cur] = st[top], cur = st[top--];
      else if (isCon(L[st[top]], i)) {
        type[++cnt] = true, L[cnt] = L[st[top]], R[cnt] = i, q[cnt] = L[cur];
        fa[st[top--]] = fa[cur] = cnt, cur = cnt;
      } else {
        fa[cur] = ++cnt;
        while (top && !isCon(L[st[top]], i)) fa[st[top--]] = cnt;
        L[cnt] = L[st[top]], R[cnt] = i, fa[st[top--]] = cnt, cur = cnt;
      }
    }
    st[++top] = cur;
    Tr.update(1, 1, n, 1, i, -1);
  }
  rt = st[1];
}
void dfs1(int u) {
  sz[u] = 1;
  if (type[u])
    sum[u] = 1LL * ((int)E[u].size()) * ((int)E[u].size() - 1) / 2;
  else
    sum[u] = 1;
  for (const auto &v : E[u]) {
    dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v], sum[u] += sum[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
  if (L[u] == R[u]) return;
  int sz = E[u].size();
  sumS[E[u][0]] = sum[E[u][0]];
  for (int i = 1; i < sz; ++i)
    pre[E[u][i]] = pre[E[u][i - 1]] + sum[E[u][i - 1]] + (type[u] ? i - 1 : 0),
    sc[E[u][i]] = i, sumS[E[u][i]] = sumS[E[u][i - 1]] + sum[E[u][i]];
  for (int i = sz - 2; ~i; --i)
    suf[E[u][i]] =
        suf[E[u][i + 1]] + sum[E[u][i + 1]] + (type[u] ? sz - i - 2 : 0);
}
void dfs2(int u, int tp) {
  top[u] = tp, dfn[u] = ++dfnc, rid[dfnc] = u;
  if (son[u]) pre[son[u]] += pre[u], suf[son[u]] += suf[u], dfs2(son[u], tp);
  for (const auto &v : E[u])
    if (v != son[u]) pre[v] += pre[u], suf[v] += suf[u], dfs2(v, v);
}
inline int LCA(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
    u = fa[top[u]];
  }
  return dep[u] < dep[v] ? u : v;
}
inline int Kth(int u, int K) {
  while (K >= dep[u] - dep[top[u]] + 1)
    K -= dep[u] - dep[top[u]] + 1, u = fa[top[u]];
  return rid[dfn[u] - K];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  rqy.init(), buildACTree();
  for (int i = 1; i <= cnt; ++i)
    if (fa[i]) E[fa[i]].emplace_back(i);
  dep[rt] = 1, dfs1(rt), dfs2(rt, rt);
  scanf("%d", &Q);
  for (int i = 1, L, R; i <= Q; ++i) {
    scanf("%d%d", &L, &R), --L, ++R;
    int x = id[L], y = id[R];
    if (!L && R > n) {
      printf("%lld\n", sum[rt]);
      continue;
    }
    if (!L) {
      int lca = rt, yk = Kth(y, dep[y] - dep[lca] - 1), t = sc[yk];
      printf("%lld\n", (pre[y] - pre[yk]) + (sumS[yk] - sum[yk]) +
                           (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
      continue;
    }
    if (R > n) {
      int lca = rt, xk = Kth(x, dep[x] - dep[lca] - 1),
          t = (int)E[lca].size() - sc[xk] - 1;
      printf("%lld\n", (suf[x] - suf[xk]) + (sumS[E[lca].back()] - sumS[xk]) +
                           (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
      continue;
    }
    int lca = LCA(x, y), xk = Kth(x, dep[x] - dep[lca] - 1),
        yk = Kth(y, dep[y] - dep[lca] - 1), t = sc[yk] - sc[xk] - 1;
    printf("%lld\n", (suf[x] - suf[xk]) + (pre[y] - pre[yk]) +
                         (sumS[yk] - sumS[xk] - sum[yk]) +
                         (type[lca] ? 1LL * t * (t - 1) / 2 : 0));
  }
  return 0;
}

```