#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 120000;
const int MAXQ = 120000;
const int MAXB = MAXN;
const int MAXS = 4 * MAXN;
int n;
int a[MAXN];
int nq;
int ql[MAXQ], qr[MAXQ];
long long qans[MAXQ];
int bsz, nb;
int bhist[MAXB];
int bmx[MAXB], bmxcnt[MAXB];
int bval[MAXN], blazy[MAXB];
void bpush(int b) {
  for (int i = b * bsz; i < (b + 1) * bsz && i < n; ++i) bval[i] += blazy[b];
  blazy[b] = 0;
}
void bpull(int b) {
  bmx[b] = INT_MIN, bmxcnt[b] = 0;
  for (int i = b * bsz; i < (b + 1) * bsz && i < n; ++i)
    if (bval[i] > bmx[b])
      bmx[b] = bval[i], bmxcnt[b] = 1;
    else if (bval[i] == bmx[b])
      ++bmxcnt[b];
}
void bmod(int l, int r, int by) {
  if (l % bsz != 0) {
    int b = l / bsz;
    bpush(b);
    while (l <= r && l % bsz != 0) bval[l] += by, ++l;
    bpull(b);
    if (l > r) return;
  }
  if (r % bsz != bsz - 1) {
    int b = r / bsz;
    bpush(b);
    while (l <= r && r % bsz != bsz - 1) bval[r] += by, --r;
    bpull(b);
    if (l > r) return;
  }
  for (int b = (l / bsz); b <= (r / bsz); ++b) blazy[b] += by;
}
void brec(int l, int r) {
  if (l % bsz != 0) {
    int b = l / bsz;
    bpush(b);
    while (l <= r && l % bsz != 0) bhist[b] += bval[l] == 0 ? 1 : 0, ++l;
    bpull(b);
    if (l > r) return;
  }
  if (r % bsz != bsz - 1) {
    int b = r / bsz;
    bpush(b);
    while (l <= r && r % bsz != bsz - 1) bhist[b] += bval[r] == 0 ? 1 : 0, --r;
    bpull(b);
    if (l > r) return;
  }
  for (int b = (l / bsz); b <= (r / bsz); ++b)
    if (bmx[b] + blazy[b] == 0) bhist[b] += bmxcnt[b];
}
int smx[MAXS], scnt[MAXS], slazy[MAXS];
void sapply(int x, int by) { smx[x] += by, slazy[x] += by; }
void spush(int x) {
  if (slazy[x] != 0)
    sapply(2 * x + 1, slazy[x]), sapply(2 * x + 2, slazy[x]), slazy[x] = 0;
}
void spull(int x) {
  smx[x] = max(smx[2 * x + 1], smx[2 * x + 2]);
  scnt[x] = (smx[2 * x + 1] == smx[x] ? scnt[2 * x + 1] : 0) +
            (smx[2 * x + 2] == smx[x] ? scnt[2 * x + 2] : 0);
}
void sinit(int x, int l, int r) {
  slazy[x] = 0;
  if (l == r) {
    smx[x] = 0, scnt[x] = 1;
  } else {
    int m = l + (r - l) / 2;
    sinit(2 * x + 1, l, m);
    sinit(2 * x + 2, m + 1, r);
    spull(x);
  }
}
void smod(int x, int l, int r, int L, int R, int BY) {
  if (L <= l && r <= R) {
    sapply(x, BY);
  } else {
    spush(x);
    int m = l + (r - l) / 2;
    if (L <= m) smod(2 * x + 1, l, m, L, R, BY);
    if (m + 1 <= R) smod(2 * x + 2, m + 1, r, L, R, BY);
    spull(x);
  }
}
int sget(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    return smx[x] == 0 ? scnt[x] : 0;
  } else {
    spush(x);
    int m = l + (r - l) / 2;
    int ret = 0;
    if (L <= m) ret += sget(2 * x + 1, l, m, L, R);
    if (m + 1 <= R) ret += sget(2 * x + 2, m + 1, r, L, R);
    spull(x);
    return ret;
  }
}
int mn[MAXN], nmn;
int mx[MAXN], nmx;
vector<int> qlft[MAXN];
vector<int> qrgt[MAXN];
void solve() {
  for (int i = (0); i < (n); ++i) qlft[i].clear(), qrgt[i].clear();
  bsz = (int)ceil(sqrt(1.0 * n * n / (n + nq * log(n) / log(2))));
  nb = (n + bsz - 1) / bsz;
  for (int i = (0); i < (nq); ++i) qlft[ql[i]].push_back(i);
  for (int i = (0); i < (nq); ++i)
    for (int r = ((qr[i] + 1) / bsz * bsz); r <= (qr[i]); ++r)
      qrgt[r].push_back(i);
  for (int i = (0); i < (nq); ++i) qans[i] = 0;
  nmn = nmx = 0;
  for (int i = (0); i < (n); ++i) bval[i] = 0;
  for (int b = (0); b < (nb); ++b) blazy[b] = bhist[b] = 0, bpull(b);
  for (int i = n - 1; i >= 0; --i) {
    while (nmn > 0 && a[mn[nmn - 1]] > a[i])
      bmod(mn[nmn - 1], nmn == 1 ? n - 1 : mn[nmn - 2] - 1,
           a[i] - a[mn[nmn - 1]]),
          --nmn;
    while (nmx > 0 && a[mx[nmx - 1]] < a[i])
      bmod(mx[nmx - 1], nmx == 1 ? n - 1 : mx[nmx - 2] - 1,
           a[mx[nmx - 1]] - a[i]),
          --nmx;
    if (i != n - 1) bmod(i + 1, n - 1, 1);
    mn[nmn++] = i, mx[nmx++] = i;
    brec(i, n - 1);
    for (int j = (0); j < (((int)(qlft[i]).size())); ++j) {
      int id = qlft[i][j];
      for (int b = (0); b < ((qr[id] + 1) / bsz); ++b) qans[id] += bhist[b];
    }
  }
  nmn = nmx = 0;
  sinit(0, 0, n - 1);
  for (int i = (0); i < (n); ++i) {
    while (nmn > 0 && a[mn[nmn - 1]] > a[i])
      smod(0, 0, n - 1, nmn == 1 ? 0 : mn[nmn - 2] + 1, mn[nmn - 1],
           a[i] - a[mn[nmn - 1]]),
          --nmn;
    while (nmx > 0 && a[mx[nmx - 1]] < a[i])
      smod(0, 0, n - 1, nmx == 1 ? 0 : mx[nmx - 2] + 1, mx[nmx - 1],
           a[mx[nmx - 1]] - a[i]),
          --nmx;
    if (i != 0) smod(0, 0, n - 1, 0, i - 1, 1);
    mn[nmn++] = i, mx[nmx++] = i;
    for (int j = (0); j < (((int)(qrgt[i]).size())); ++j) {
      int id = qrgt[i][j];
      int cur = sget(0, 0, n - 1, ql[id], i);
      qans[id] += cur;
    }
  }
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]), --a[i];
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d", &ql[i], &qr[i]), --ql[i], --qr[i];
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
long long bfans[MAXQ];
void bfsolve() {
  for (int i = (0); i < (nq); ++i) bfans[i] = 0;
  for (int l = (0); l < (n); ++l)
    for (int r = (l); r < (n); ++r) {
      int mn = a[l], mx = a[l];
      for (int i = (l); i <= (r); ++i) mn = min(mn, a[i]), mx = max(mx, a[i]);
      if (r - l != mx - mn) continue;
      for (int i = (0); i < (nq); ++i)
        if (ql[i] <= l && r <= qr[i]) ++bfans[i];
    }
}
void stress() {
  for (int rep = (0); rep < (10000); ++rep) {
    n = 100;
    for (int i = (0); i < (n); ++i) a[i] = i;
    random_shuffle(a, a + n);
    nq = 100;
    for (int i = (0); i < (nq); ++i) {
      ql[i] = rand() % n, qr[i] = rand() % n;
      if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    solve();
    bfsolve();
    bool ok = true;
    for (int i = (0); i < (nq); ++i)
      if (qans[i] != bfans[i]) ok = false;
    if (ok) {
      printf(".");
      continue;
    }
    printf("err\n");
    printf("%d\n", n);
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", a[i] + 1);
    }
    puts("");
    printf("%d\n", nq);
    for (int i = (0); i < (nq); ++i) printf("%d %d\n", ql[i] + 1, qr[i] + 1);
    printf("have:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", qans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", bfans[i]);
    puts("");
    break;
  }
}
int main() {
  run();
  return 0;
}

### Prompt

Create a solution in Cpp for 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 gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 120000;
const int MAXQ = 120000;
const int MAXB = MAXN;
const int MAXS = 4 * MAXN;
int n;
int a[MAXN];
int nq;
int ql[MAXQ], qr[MAXQ];
long long qans[MAXQ];
int bsz, nb;
int bhist[MAXB];
int bmx[MAXB], bmxcnt[MAXB];
int bval[MAXN], blazy[MAXB];
void bpush(int b) {
  for (int i = b * bsz; i < (b + 1) * bsz && i < n; ++i) bval[i] += blazy[b];
  blazy[b] = 0;
}
void bpull(int b) {
  bmx[b] = INT_MIN, bmxcnt[b] = 0;
  for (int i = b * bsz; i < (b + 1) * bsz && i < n; ++i)
    if (bval[i] > bmx[b])
      bmx[b] = bval[i], bmxcnt[b] = 1;
    else if (bval[i] == bmx[b])
      ++bmxcnt[b];
}
void bmod(int l, int r, int by) {
  if (l % bsz != 0) {
    int b = l / bsz;
    bpush(b);
    while (l <= r && l % bsz != 0) bval[l] += by, ++l;
    bpull(b);
    if (l > r) return;
  }
  if (r % bsz != bsz - 1) {
    int b = r / bsz;
    bpush(b);
    while (l <= r && r % bsz != bsz - 1) bval[r] += by, --r;
    bpull(b);
    if (l > r) return;
  }
  for (int b = (l / bsz); b <= (r / bsz); ++b) blazy[b] += by;
}
void brec(int l, int r) {
  if (l % bsz != 0) {
    int b = l / bsz;
    bpush(b);
    while (l <= r && l % bsz != 0) bhist[b] += bval[l] == 0 ? 1 : 0, ++l;
    bpull(b);
    if (l > r) return;
  }
  if (r % bsz != bsz - 1) {
    int b = r / bsz;
    bpush(b);
    while (l <= r && r % bsz != bsz - 1) bhist[b] += bval[r] == 0 ? 1 : 0, --r;
    bpull(b);
    if (l > r) return;
  }
  for (int b = (l / bsz); b <= (r / bsz); ++b)
    if (bmx[b] + blazy[b] == 0) bhist[b] += bmxcnt[b];
}
int smx[MAXS], scnt[MAXS], slazy[MAXS];
void sapply(int x, int by) { smx[x] += by, slazy[x] += by; }
void spush(int x) {
  if (slazy[x] != 0)
    sapply(2 * x + 1, slazy[x]), sapply(2 * x + 2, slazy[x]), slazy[x] = 0;
}
void spull(int x) {
  smx[x] = max(smx[2 * x + 1], smx[2 * x + 2]);
  scnt[x] = (smx[2 * x + 1] == smx[x] ? scnt[2 * x + 1] : 0) +
            (smx[2 * x + 2] == smx[x] ? scnt[2 * x + 2] : 0);
}
void sinit(int x, int l, int r) {
  slazy[x] = 0;
  if (l == r) {
    smx[x] = 0, scnt[x] = 1;
  } else {
    int m = l + (r - l) / 2;
    sinit(2 * x + 1, l, m);
    sinit(2 * x + 2, m + 1, r);
    spull(x);
  }
}
void smod(int x, int l, int r, int L, int R, int BY) {
  if (L <= l && r <= R) {
    sapply(x, BY);
  } else {
    spush(x);
    int m = l + (r - l) / 2;
    if (L <= m) smod(2 * x + 1, l, m, L, R, BY);
    if (m + 1 <= R) smod(2 * x + 2, m + 1, r, L, R, BY);
    spull(x);
  }
}
int sget(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    return smx[x] == 0 ? scnt[x] : 0;
  } else {
    spush(x);
    int m = l + (r - l) / 2;
    int ret = 0;
    if (L <= m) ret += sget(2 * x + 1, l, m, L, R);
    if (m + 1 <= R) ret += sget(2 * x + 2, m + 1, r, L, R);
    spull(x);
    return ret;
  }
}
int mn[MAXN], nmn;
int mx[MAXN], nmx;
vector<int> qlft[MAXN];
vector<int> qrgt[MAXN];
void solve() {
  for (int i = (0); i < (n); ++i) qlft[i].clear(), qrgt[i].clear();
  bsz = (int)ceil(sqrt(1.0 * n * n / (n + nq * log(n) / log(2))));
  nb = (n + bsz - 1) / bsz;
  for (int i = (0); i < (nq); ++i) qlft[ql[i]].push_back(i);
  for (int i = (0); i < (nq); ++i)
    for (int r = ((qr[i] + 1) / bsz * bsz); r <= (qr[i]); ++r)
      qrgt[r].push_back(i);
  for (int i = (0); i < (nq); ++i) qans[i] = 0;
  nmn = nmx = 0;
  for (int i = (0); i < (n); ++i) bval[i] = 0;
  for (int b = (0); b < (nb); ++b) blazy[b] = bhist[b] = 0, bpull(b);
  for (int i = n - 1; i >= 0; --i) {
    while (nmn > 0 && a[mn[nmn - 1]] > a[i])
      bmod(mn[nmn - 1], nmn == 1 ? n - 1 : mn[nmn - 2] - 1,
           a[i] - a[mn[nmn - 1]]),
          --nmn;
    while (nmx > 0 && a[mx[nmx - 1]] < a[i])
      bmod(mx[nmx - 1], nmx == 1 ? n - 1 : mx[nmx - 2] - 1,
           a[mx[nmx - 1]] - a[i]),
          --nmx;
    if (i != n - 1) bmod(i + 1, n - 1, 1);
    mn[nmn++] = i, mx[nmx++] = i;
    brec(i, n - 1);
    for (int j = (0); j < (((int)(qlft[i]).size())); ++j) {
      int id = qlft[i][j];
      for (int b = (0); b < ((qr[id] + 1) / bsz); ++b) qans[id] += bhist[b];
    }
  }
  nmn = nmx = 0;
  sinit(0, 0, n - 1);
  for (int i = (0); i < (n); ++i) {
    while (nmn > 0 && a[mn[nmn - 1]] > a[i])
      smod(0, 0, n - 1, nmn == 1 ? 0 : mn[nmn - 2] + 1, mn[nmn - 1],
           a[i] - a[mn[nmn - 1]]),
          --nmn;
    while (nmx > 0 && a[mx[nmx - 1]] < a[i])
      smod(0, 0, n - 1, nmx == 1 ? 0 : mx[nmx - 2] + 1, mx[nmx - 1],
           a[mx[nmx - 1]] - a[i]),
          --nmx;
    if (i != 0) smod(0, 0, n - 1, 0, i - 1, 1);
    mn[nmn++] = i, mx[nmx++] = i;
    for (int j = (0); j < (((int)(qrgt[i]).size())); ++j) {
      int id = qrgt[i][j];
      int cur = sget(0, 0, n - 1, ql[id], i);
      qans[id] += cur;
    }
  }
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]), --a[i];
  scanf("%d", &nq);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d", &ql[i], &qr[i]), --ql[i], --qr[i];
  solve();
  for (int i = (0); i < (nq); ++i) printf("%lld\n", qans[i]);
}
long long bfans[MAXQ];
void bfsolve() {
  for (int i = (0); i < (nq); ++i) bfans[i] = 0;
  for (int l = (0); l < (n); ++l)
    for (int r = (l); r < (n); ++r) {
      int mn = a[l], mx = a[l];
      for (int i = (l); i <= (r); ++i) mn = min(mn, a[i]), mx = max(mx, a[i]);
      if (r - l != mx - mn) continue;
      for (int i = (0); i < (nq); ++i)
        if (ql[i] <= l && r <= qr[i]) ++bfans[i];
    }
}
void stress() {
  for (int rep = (0); rep < (10000); ++rep) {
    n = 100;
    for (int i = (0); i < (n); ++i) a[i] = i;
    random_shuffle(a, a + n);
    nq = 100;
    for (int i = (0); i < (nq); ++i) {
      ql[i] = rand() % n, qr[i] = rand() % n;
      if (ql[i] > qr[i]) swap(ql[i], qr[i]);
    }
    solve();
    bfsolve();
    bool ok = true;
    for (int i = (0); i < (nq); ++i)
      if (qans[i] != bfans[i]) ok = false;
    if (ok) {
      printf(".");
      continue;
    }
    printf("err\n");
    printf("%d\n", n);
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", a[i] + 1);
    }
    puts("");
    printf("%d\n", nq);
    for (int i = (0); i < (nq); ++i) printf("%d %d\n", ql[i] + 1, qr[i] + 1);
    printf("have:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", qans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (nq); ++i) printf(" %lld", bfans[i]);
    puts("");
    break;
  }
}
int main() {
  run();
  return 0;
}

```