#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long w = 0, flg = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      flg = -1;
    }
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    w = w * 10 + ch - '0', ch = getchar();
  }
  return w * flg;
}
long long n, a[120010], q;
long long stmx[120010][20], stmn[120010][20], lg2[120010];
void init() {
  lg2[0] = -1;
  for (long long i = (1); i <= (n); i++)
    lg2[i] = lg2[i >> 1] + 1, stmx[i][0] = stmn[i][0] = a[i];
  for (long long i = (1); i <= (18); i++) {
    for (long long j = (1); j <= (n); j++) {
      if (j + (1 << i) - 1 > n) break;
      stmx[j][i] = max(stmx[j][i - 1], stmx[j + (1 << (i - 1))][i - 1]);
      stmn[j][i] = min(stmn[j][i - 1], stmn[j + (1 << (i - 1))][i - 1]);
    }
  }
}
long long mx_query(long long ql, long long qr) {
  return max(stmx[ql][lg2[qr - ql + 1]],
             stmx[qr - (1 << lg2[qr - ql + 1]) + 1][lg2[qr - ql + 1]]);
}
long long mn_query(long long ql, long long qr) {
  return min(stmn[ql][lg2[qr - ql + 1]],
             stmn[qr - (1 << lg2[qr - ql + 1]) + 1][lg2[qr - ql + 1]]);
}
long long mn[120010 << 2], tag[120010 << 2];
void push_up(long long now) {
  mn[now] = min(mn[(now << 1)], mn[(now << 1 | 1)]);
}
void push_down(long long now) {
  if (tag[now]) {
    tag[(now << 1)] += tag[now], tag[(now << 1 | 1)] += tag[now];
    mn[(now << 1)] += tag[now], mn[(now << 1 | 1)] += tag[now];
    tag[now] = 0;
  }
}
void update(long long now, long long l, long long r, long long ql, long long qr,
            long long d) {
  if (ql <= l && qr >= r)
    tag[now] += d, mn[now] += d;
  else {
    push_down(now);
    if (ql <= ((l + r) >> 1)) update((now << 1), l, ((l + r) >> 1), ql, qr, d);
    if (qr > ((l + r) >> 1))
      update((now << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, d);
    push_up(now);
  }
}
long long query(long long now, long long l, long long r) {
  if (l == r)
    return l;
  else {
    push_down(now);
    if (!mn[(now << 1)])
      return query((now << 1), l, ((l + r) >> 1));
    else
      return query((now << 1 | 1), ((l + r) >> 1) + 1, r);
  }
}
long long head[120010 * 2], ednum;
struct edge {
  long long nxt, to;
} ed[120010 * 2];
void add_Edge(long long u, long long v) {
  ednum++;
  ed[ednum].nxt = head[u], ed[ednum].to = v;
  head[u] = ednum;
}
long long L[120010 * 2], R[120010 * 2], M[120010 * 2], typ[120010 * 2], cnt;
long long st1[120010], tp1, st2[120010], tp2, sta[120010 * 2], tpf, num[120010];
bool ck(long long ql, long long qr) {
  return mx_query(ql, qr) - mn_query(ql, qr) == qr - ql;
}
void build() {
  init();
  for (long long i = (1); i <= (n); i++) {
    while (tp1 && a[i] > a[st1[tp1]])
      update(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], -a[st1[tp1]]), tp1--;
    while (tp2 && a[i] < a[st2[tp2]])
      update(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], a[st2[tp2]]), tp2--;
    update(1, 1, n, st1[tp1] + 1, i, a[i]),
        update(1, 1, n, st2[tp2] + 1, i, -a[i]);
    st1[++tp1] = i, st2[++tp2] = i;
    long long now = ++cnt, le = query(1, 1, n);
    L[cnt] = R[cnt] = i, num[i] = cnt;
    while (tpf && L[sta[tpf]] >= le) {
      if (typ[sta[tpf]] && ck(M[sta[tpf]], i)) {
        R[sta[tpf]] = i;
        add_Edge(sta[tpf], now);
        now = sta[tpf--];
      } else if (ck(L[sta[tpf]], i)) {
        typ[++cnt] = 1, L[cnt] = L[sta[tpf]], R[cnt] = i, M[cnt] = L[now];
        add_Edge(cnt, now), add_Edge(cnt, sta[tpf]);
        tpf--, now = cnt;
      } else {
        cnt++;
        add_Edge(cnt, now);
        do add_Edge(cnt, sta[tpf]), tpf--;
        while (tpf && !ck(L[sta[tpf]], i));
        add_Edge(cnt, sta[tpf]);
        L[cnt] = L[sta[tpf]], R[cnt] = i, tpf--, now = cnt;
      }
    }
    sta[++tpf] = now;
    update(1, 1, n, 1, i, -1);
  }
}
long long fa[120010 * 2][20], dep[120010 * 2], son[120010 * 2];
long long w[120010 * 2];
long long presum[120010 * 2][20], sucsum[120010 * 2][20], pre[120010 * 2],
    suc[120010 * 2], id[120010 * 2];
void dfs1(long long u) {
  long long tot = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    long long v = ed[i].to;
    dfs1(v);
    w[u] += w[v], tot++;
  }
  if (typ[u])
    w[u] += tot * (tot - 1) / 2;
  else
    w[u]++;
}
bool cmp(long long x, long long y) { return L[x] > L[y]; }
void dfs2(long long u, long long dad) {
  fa[u][0] = dad, dep[u] = dep[dad] + 1;
  for (long long i = (1); i <= (19); i++) {
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
    presum[u][i] = presum[u][i - 1] + presum[fa[u][i - 1]][i - 1];
    sucsum[u][i] = sucsum[u][i - 1] + sucsum[fa[u][i - 1]][i - 1];
  }
  long long tot = 0;
  long long sum = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    son[++tot] = ed[i].to;
  }
  sort(son + 1, son + tot + 1, cmp);
  for (long long i = (1); i <= (tot); i++) {
    long long v = son[i];
    if (typ[u])
      sucsum[v][0] = (i - 1) * ((i - 1) - 1) / 2 + sum;
    else
      sucsum[v][0] = sum;
    sum += w[v];
    if (typ[u])
      suc[v] = i * (i - 1) / 2 + sum;
    else
      suc[v] = sum;
  }
  sum = 0;
  for (long long i = (tot); i >= (1); i--) {
    long long v = son[i];
    if (typ[u])
      presum[v][0] = (tot - i) * ((tot - i) - 1) / 2 + sum;
    else
      presum[v][0] = sum;
    sum += w[v], id[v] = tot - i + 1;
    if (typ[u])
      pre[v] = (tot - i + 1) * (tot - i) / 2 + sum;
    else
      pre[v] = sum;
  }
  tot = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    dfs2(ed[i].to, u);
  }
}
long long getlca(long long u, long long v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (long long i = (19); i >= (0); i--)
    if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
  if (u == v) return u;
  for (long long i = (19); i >= (0); i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
long long pre_getsum(long long u, long long v) {
  long long re = 0;
  long long tmp = dep[v] + 1;
  for (long long i = (19); i >= (0); i--) {
    long long ttmp = 1 << i;
    if (dep[fa[u][i]] >= tmp && (dep[u] - dep[v] >= ttmp))
      re += presum[u][i], u = fa[u][i];
  }
  return re;
}
long long suc_getsum(long long u, long long v) {
  long long re = 0;
  long long tmp = dep[v] + 1;
  for (long long i = (19); i >= (0); i--) {
    long long ttmp = 1 << i;
    if (dep[fa[u][i]] >= tmp && (dep[u] - dep[v] >= ttmp)) {
      re += sucsum[u][i], u = fa[u][i];
    }
  }
  return re;
}
long long getson(long long u, long long v) {
  for (long long i = (19); i >= (0); i--)
    if (dep[fa[u][i]] > dep[v]) u = fa[u][i];
  return u;
}
long long re_query(long long u, long long v, long long lca) {
  u = getson(u, lca), v = getson(v, lca);
  long long lid = id[u], rid = id[v];
  if (lid > rid) swap(lid, rid), swap(u, v);
  if (typ[lca])
    return presum[v][0] - pre[u] - lid * (rid - lid - 1);
  else
    return presum[v][0] - pre[u];
}
int main() {
  n = read();
  for (long long i = (1); i <= (n); i++) a[i] = read();
  build();
  dfs1(sta[tpf]);
  dfs2(sta[tpf], 0);
  q = read();
  for (long long i = (1); i <= (q); i++) {
    long long ql = read(), qr = read();
    if (ql == 1 && qr == n)
      printf("%lld\n", w[sta[tpf]]);
    else if (ql == 1) {
      long long lca = getlca(num[1], num[qr + 1]);
      printf("%lld\n", pre_getsum(num[qr + 1], fa[lca][0]));
    } else if (qr == n) {
      long long lca = getlca(num[ql - 1], num[n]);
      printf("%lld\n", suc_getsum(num[ql - 1], fa[lca][0]));
    } else {
      ql--, qr++;
      ql = num[ql], qr = num[qr];
      long long lca = getlca(ql, qr);
      long long re = suc_getsum(ql, lca) + pre_getsum(qr, lca);
      re += re_query(ql, qr, lca);
      printf("%lld\n", re);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write 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>
using namespace std;
long long read() {
  long long w = 0, flg = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      flg = -1;
    }
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    w = w * 10 + ch - '0', ch = getchar();
  }
  return w * flg;
}
long long n, a[120010], q;
long long stmx[120010][20], stmn[120010][20], lg2[120010];
void init() {
  lg2[0] = -1;
  for (long long i = (1); i <= (n); i++)
    lg2[i] = lg2[i >> 1] + 1, stmx[i][0] = stmn[i][0] = a[i];
  for (long long i = (1); i <= (18); i++) {
    for (long long j = (1); j <= (n); j++) {
      if (j + (1 << i) - 1 > n) break;
      stmx[j][i] = max(stmx[j][i - 1], stmx[j + (1 << (i - 1))][i - 1]);
      stmn[j][i] = min(stmn[j][i - 1], stmn[j + (1 << (i - 1))][i - 1]);
    }
  }
}
long long mx_query(long long ql, long long qr) {
  return max(stmx[ql][lg2[qr - ql + 1]],
             stmx[qr - (1 << lg2[qr - ql + 1]) + 1][lg2[qr - ql + 1]]);
}
long long mn_query(long long ql, long long qr) {
  return min(stmn[ql][lg2[qr - ql + 1]],
             stmn[qr - (1 << lg2[qr - ql + 1]) + 1][lg2[qr - ql + 1]]);
}
long long mn[120010 << 2], tag[120010 << 2];
void push_up(long long now) {
  mn[now] = min(mn[(now << 1)], mn[(now << 1 | 1)]);
}
void push_down(long long now) {
  if (tag[now]) {
    tag[(now << 1)] += tag[now], tag[(now << 1 | 1)] += tag[now];
    mn[(now << 1)] += tag[now], mn[(now << 1 | 1)] += tag[now];
    tag[now] = 0;
  }
}
void update(long long now, long long l, long long r, long long ql, long long qr,
            long long d) {
  if (ql <= l && qr >= r)
    tag[now] += d, mn[now] += d;
  else {
    push_down(now);
    if (ql <= ((l + r) >> 1)) update((now << 1), l, ((l + r) >> 1), ql, qr, d);
    if (qr > ((l + r) >> 1))
      update((now << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, d);
    push_up(now);
  }
}
long long query(long long now, long long l, long long r) {
  if (l == r)
    return l;
  else {
    push_down(now);
    if (!mn[(now << 1)])
      return query((now << 1), l, ((l + r) >> 1));
    else
      return query((now << 1 | 1), ((l + r) >> 1) + 1, r);
  }
}
long long head[120010 * 2], ednum;
struct edge {
  long long nxt, to;
} ed[120010 * 2];
void add_Edge(long long u, long long v) {
  ednum++;
  ed[ednum].nxt = head[u], ed[ednum].to = v;
  head[u] = ednum;
}
long long L[120010 * 2], R[120010 * 2], M[120010 * 2], typ[120010 * 2], cnt;
long long st1[120010], tp1, st2[120010], tp2, sta[120010 * 2], tpf, num[120010];
bool ck(long long ql, long long qr) {
  return mx_query(ql, qr) - mn_query(ql, qr) == qr - ql;
}
void build() {
  init();
  for (long long i = (1); i <= (n); i++) {
    while (tp1 && a[i] > a[st1[tp1]])
      update(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], -a[st1[tp1]]), tp1--;
    while (tp2 && a[i] < a[st2[tp2]])
      update(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], a[st2[tp2]]), tp2--;
    update(1, 1, n, st1[tp1] + 1, i, a[i]),
        update(1, 1, n, st2[tp2] + 1, i, -a[i]);
    st1[++tp1] = i, st2[++tp2] = i;
    long long now = ++cnt, le = query(1, 1, n);
    L[cnt] = R[cnt] = i, num[i] = cnt;
    while (tpf && L[sta[tpf]] >= le) {
      if (typ[sta[tpf]] && ck(M[sta[tpf]], i)) {
        R[sta[tpf]] = i;
        add_Edge(sta[tpf], now);
        now = sta[tpf--];
      } else if (ck(L[sta[tpf]], i)) {
        typ[++cnt] = 1, L[cnt] = L[sta[tpf]], R[cnt] = i, M[cnt] = L[now];
        add_Edge(cnt, now), add_Edge(cnt, sta[tpf]);
        tpf--, now = cnt;
      } else {
        cnt++;
        add_Edge(cnt, now);
        do add_Edge(cnt, sta[tpf]), tpf--;
        while (tpf && !ck(L[sta[tpf]], i));
        add_Edge(cnt, sta[tpf]);
        L[cnt] = L[sta[tpf]], R[cnt] = i, tpf--, now = cnt;
      }
    }
    sta[++tpf] = now;
    update(1, 1, n, 1, i, -1);
  }
}
long long fa[120010 * 2][20], dep[120010 * 2], son[120010 * 2];
long long w[120010 * 2];
long long presum[120010 * 2][20], sucsum[120010 * 2][20], pre[120010 * 2],
    suc[120010 * 2], id[120010 * 2];
void dfs1(long long u) {
  long long tot = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    long long v = ed[i].to;
    dfs1(v);
    w[u] += w[v], tot++;
  }
  if (typ[u])
    w[u] += tot * (tot - 1) / 2;
  else
    w[u]++;
}
bool cmp(long long x, long long y) { return L[x] > L[y]; }
void dfs2(long long u, long long dad) {
  fa[u][0] = dad, dep[u] = dep[dad] + 1;
  for (long long i = (1); i <= (19); i++) {
    fa[u][i] = fa[fa[u][i - 1]][i - 1];
    presum[u][i] = presum[u][i - 1] + presum[fa[u][i - 1]][i - 1];
    sucsum[u][i] = sucsum[u][i - 1] + sucsum[fa[u][i - 1]][i - 1];
  }
  long long tot = 0;
  long long sum = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    son[++tot] = ed[i].to;
  }
  sort(son + 1, son + tot + 1, cmp);
  for (long long i = (1); i <= (tot); i++) {
    long long v = son[i];
    if (typ[u])
      sucsum[v][0] = (i - 1) * ((i - 1) - 1) / 2 + sum;
    else
      sucsum[v][0] = sum;
    sum += w[v];
    if (typ[u])
      suc[v] = i * (i - 1) / 2 + sum;
    else
      suc[v] = sum;
  }
  sum = 0;
  for (long long i = (tot); i >= (1); i--) {
    long long v = son[i];
    if (typ[u])
      presum[v][0] = (tot - i) * ((tot - i) - 1) / 2 + sum;
    else
      presum[v][0] = sum;
    sum += w[v], id[v] = tot - i + 1;
    if (typ[u])
      pre[v] = (tot - i + 1) * (tot - i) / 2 + sum;
    else
      pre[v] = sum;
  }
  tot = 0;
  for (long long i = head[u]; i; i = ed[i].nxt) {
    dfs2(ed[i].to, u);
  }
}
long long getlca(long long u, long long v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (long long i = (19); i >= (0); i--)
    if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
  if (u == v) return u;
  for (long long i = (19); i >= (0); i--)
    if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}
long long pre_getsum(long long u, long long v) {
  long long re = 0;
  long long tmp = dep[v] + 1;
  for (long long i = (19); i >= (0); i--) {
    long long ttmp = 1 << i;
    if (dep[fa[u][i]] >= tmp && (dep[u] - dep[v] >= ttmp))
      re += presum[u][i], u = fa[u][i];
  }
  return re;
}
long long suc_getsum(long long u, long long v) {
  long long re = 0;
  long long tmp = dep[v] + 1;
  for (long long i = (19); i >= (0); i--) {
    long long ttmp = 1 << i;
    if (dep[fa[u][i]] >= tmp && (dep[u] - dep[v] >= ttmp)) {
      re += sucsum[u][i], u = fa[u][i];
    }
  }
  return re;
}
long long getson(long long u, long long v) {
  for (long long i = (19); i >= (0); i--)
    if (dep[fa[u][i]] > dep[v]) u = fa[u][i];
  return u;
}
long long re_query(long long u, long long v, long long lca) {
  u = getson(u, lca), v = getson(v, lca);
  long long lid = id[u], rid = id[v];
  if (lid > rid) swap(lid, rid), swap(u, v);
  if (typ[lca])
    return presum[v][0] - pre[u] - lid * (rid - lid - 1);
  else
    return presum[v][0] - pre[u];
}
int main() {
  n = read();
  for (long long i = (1); i <= (n); i++) a[i] = read();
  build();
  dfs1(sta[tpf]);
  dfs2(sta[tpf], 0);
  q = read();
  for (long long i = (1); i <= (q); i++) {
    long long ql = read(), qr = read();
    if (ql == 1 && qr == n)
      printf("%lld\n", w[sta[tpf]]);
    else if (ql == 1) {
      long long lca = getlca(num[1], num[qr + 1]);
      printf("%lld\n", pre_getsum(num[qr + 1], fa[lca][0]));
    } else if (qr == n) {
      long long lca = getlca(num[ql - 1], num[n]);
      printf("%lld\n", suc_getsum(num[ql - 1], fa[lca][0]));
    } else {
      ql--, qr++;
      ql = num[ql], qr = num[qr];
      long long lca = getlca(ql, qr);
      long long re = suc_getsum(ql, lca) + pre_getsum(qr, lca);
      re += re_query(ql, qr, lca);
      printf("%lld\n", re);
    }
  }
  return 0;
}

```