#include <bits/stdc++.h>
using namespace std;
const int N = 120000;
int n, cq, a[N + 9];
vector<int> ql[N + 9], qid[N + 9];
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  scanf("%d", &cq);
  for (int i = 1; i <= cq; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    ql[r].push_back(l);
    qid[r].push_back(i);
  }
}
vector<int> p[N + 9];
int mx[N + 9], mn[N + 9], cmx, cmn;
void Get_p() {
  for (int i = 1; i <= n; ++i) {
    p[i].push_back(0);
    for (; cmx && a[mx[cmx]] <= a[i]; --cmx) p[i].push_back(mx[cmx]);
    if (cmx) p[i].push_back(mx[cmx]);
    mx[++cmx] = i;
    for (; cmn && a[mn[cmn]] >= a[i]; --cmn) p[i].push_back(mn[cmn]);
    if (cmn) p[i].push_back(mn[cmn]);
    mn[++cmn] = i;
    sort(p[i].begin(), p[i].end());
  }
}
struct data {
  int v;
  long long cnt;
  data(int V = 0, long long Cnt = 0) {
    v = V;
    cnt = Cnt;
  }
  data operator+(const data &p) const { return data(v + p.v, cnt * p.cnt); }
};
data dmin(data a, data b) {
  return data(min(a.v, b.v), a.v == b.v  ? a.cnt + b.cnt
                             : a.v < b.v ? a.cnt
                                         : b.cnt);
}
struct tree {
  data min, hmin, add, hadd;
} tr[N * 4 + 9];
void Pushup(int k) {
  int ls = k << 1, rs = k << 1 | 1;
  tr[k].min = dmin(tr[ls].min, tr[rs].min);
  tr[k].hmin = dmin(tr[ls].hmin, tr[rs].hmin);
}
void Update_hadd(int k, data v) {
  tr[k].hmin = dmin(tr[k].hmin, tr[k].min + v);
  tr[k].hadd = dmin(tr[k].hadd, tr[k].add + v);
}
void Pushdown_hadd(int k) {
  if (!tr[k].hadd.v && !tr[k].hadd.cnt) return;
  Update_hadd(k << 1, tr[k].hadd);
  Update_hadd(k << 1 | 1, tr[k].hadd);
  tr[k].hadd = data();
}
void Update_add(int k, data v) {
  tr[k].min = tr[k].min + v;
  tr[k].add = tr[k].add + v;
}
void Pushdown_add(int k) {
  if (!tr[k].add.v && tr[k].add.cnt == 1) return;
  Update_add(k << 1, tr[k].add);
  Update_add(k << 1 | 1, tr[k].add);
  tr[k].add = data(0, 1);
}
void Pushdown(int k) {
  Pushdown_hadd(k);
  Pushdown_add(k);
}
void Build(int l, int r, int k) {
  tr[k].add = data(0, 1);
  if (l == r) {
    tr[k].min = tr[k].hmin = data(0, 1);
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, k << 1);
  Build(mid + 1, r, k << 1 | 1);
  Pushup(k);
}
void Change_add(int L, int R, data v, int l, int r, int k) {
  if (L <= l && R >= r) {
    Update_hadd(k, v);
    Update_add(k, v);
    return;
  }
  int mid = l + r >> 1;
  Pushdown(k);
  if (L <= mid) Change_add(L, R, v, l, mid, k << 1);
  if (R > mid) Change_add(L, R, v, mid + 1, r, k << 1 | 1);
  Pushup(k);
}
long long Query_cnt(int L, int R, int l, int r, int k) {
  if (L <= l && R >= r) return tr[k].hmin.cnt;
  int mid = l + r >> 1;
  long long res = 0;
  Pushdown(k);
  if (L <= mid) res += Query_cnt(L, R, l, mid, k << 1);
  if (R > mid) res += Query_cnt(L, R, mid + 1, r, k << 1 | 1);
  return res;
}
long long ans[N + 9];
void Get_ans() {
  Build(1, n, 1);
  for (int i = 1; i <= n; ++i) {
    int vmx = a[i - 1], vmn = a[i - 1];
    for (int vs = p[i].size() - 1, j = vs; j >= 1; --j)
      if (p[i][j - 1] ^ p[i][j]) {
        int t = p[i][j];
        vmx = max(vmx, a[t]);
        vmn = min(vmn, a[t]);
        Change_add(p[i][j - 1] + 1, t,
                   data(max(a[i] - vmx, 0) + max(vmn - a[i], 0) - 1, 1), 1, n,
                   1);
      }
    for (int vs = ql[i].size(), j = 0; j < vs; ++j)
      ans[qid[i][j]] = Query_cnt(ql[i][j], i, 1, n, 1);
  }
}
void work() {
  Get_p();
  Get_ans();
}
void outo() {
  for (int i = 1; i <= cq; ++i) printf("%lld\n", ans[i]);
  puts("");
}
int main() {
  into();
  work();
  outo();
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
const int N = 120000;
int n, cq, a[N + 9];
vector<int> ql[N + 9], qid[N + 9];
void into() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  scanf("%d", &cq);
  for (int i = 1; i <= cq; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    ql[r].push_back(l);
    qid[r].push_back(i);
  }
}
vector<int> p[N + 9];
int mx[N + 9], mn[N + 9], cmx, cmn;
void Get_p() {
  for (int i = 1; i <= n; ++i) {
    p[i].push_back(0);
    for (; cmx && a[mx[cmx]] <= a[i]; --cmx) p[i].push_back(mx[cmx]);
    if (cmx) p[i].push_back(mx[cmx]);
    mx[++cmx] = i;
    for (; cmn && a[mn[cmn]] >= a[i]; --cmn) p[i].push_back(mn[cmn]);
    if (cmn) p[i].push_back(mn[cmn]);
    mn[++cmn] = i;
    sort(p[i].begin(), p[i].end());
  }
}
struct data {
  int v;
  long long cnt;
  data(int V = 0, long long Cnt = 0) {
    v = V;
    cnt = Cnt;
  }
  data operator+(const data &p) const { return data(v + p.v, cnt * p.cnt); }
};
data dmin(data a, data b) {
  return data(min(a.v, b.v), a.v == b.v  ? a.cnt + b.cnt
                             : a.v < b.v ? a.cnt
                                         : b.cnt);
}
struct tree {
  data min, hmin, add, hadd;
} tr[N * 4 + 9];
void Pushup(int k) {
  int ls = k << 1, rs = k << 1 | 1;
  tr[k].min = dmin(tr[ls].min, tr[rs].min);
  tr[k].hmin = dmin(tr[ls].hmin, tr[rs].hmin);
}
void Update_hadd(int k, data v) {
  tr[k].hmin = dmin(tr[k].hmin, tr[k].min + v);
  tr[k].hadd = dmin(tr[k].hadd, tr[k].add + v);
}
void Pushdown_hadd(int k) {
  if (!tr[k].hadd.v && !tr[k].hadd.cnt) return;
  Update_hadd(k << 1, tr[k].hadd);
  Update_hadd(k << 1 | 1, tr[k].hadd);
  tr[k].hadd = data();
}
void Update_add(int k, data v) {
  tr[k].min = tr[k].min + v;
  tr[k].add = tr[k].add + v;
}
void Pushdown_add(int k) {
  if (!tr[k].add.v && tr[k].add.cnt == 1) return;
  Update_add(k << 1, tr[k].add);
  Update_add(k << 1 | 1, tr[k].add);
  tr[k].add = data(0, 1);
}
void Pushdown(int k) {
  Pushdown_hadd(k);
  Pushdown_add(k);
}
void Build(int l, int r, int k) {
  tr[k].add = data(0, 1);
  if (l == r) {
    tr[k].min = tr[k].hmin = data(0, 1);
    return;
  }
  int mid = l + r >> 1;
  Build(l, mid, k << 1);
  Build(mid + 1, r, k << 1 | 1);
  Pushup(k);
}
void Change_add(int L, int R, data v, int l, int r, int k) {
  if (L <= l && R >= r) {
    Update_hadd(k, v);
    Update_add(k, v);
    return;
  }
  int mid = l + r >> 1;
  Pushdown(k);
  if (L <= mid) Change_add(L, R, v, l, mid, k << 1);
  if (R > mid) Change_add(L, R, v, mid + 1, r, k << 1 | 1);
  Pushup(k);
}
long long Query_cnt(int L, int R, int l, int r, int k) {
  if (L <= l && R >= r) return tr[k].hmin.cnt;
  int mid = l + r >> 1;
  long long res = 0;
  Pushdown(k);
  if (L <= mid) res += Query_cnt(L, R, l, mid, k << 1);
  if (R > mid) res += Query_cnt(L, R, mid + 1, r, k << 1 | 1);
  return res;
}
long long ans[N + 9];
void Get_ans() {
  Build(1, n, 1);
  for (int i = 1; i <= n; ++i) {
    int vmx = a[i - 1], vmn = a[i - 1];
    for (int vs = p[i].size() - 1, j = vs; j >= 1; --j)
      if (p[i][j - 1] ^ p[i][j]) {
        int t = p[i][j];
        vmx = max(vmx, a[t]);
        vmn = min(vmn, a[t]);
        Change_add(p[i][j - 1] + 1, t,
                   data(max(a[i] - vmx, 0) + max(vmn - a[i], 0) - 1, 1), 1, n,
                   1);
      }
    for (int vs = ql[i].size(), j = 0; j < vs; ++j)
      ans[qid[i][j]] = Query_cnt(ql[i][j], i, 1, n, 1);
  }
}
void work() {
  Get_p();
  Get_ans();
}
void outo() {
  for (int i = 1; i <= cq; ++i) printf("%lld\n", ans[i]);
  puts("");
}
int main() {
  into();
  work();
  outo();
  return 0;
}

```