#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long Ans[120000 + 5];
int n, m, a[120000 + 5], b[120000 + 5], q[120000 + 5], top, Q[120000 + 5], Top,
    cnt, block[120000 + 5], Tag[120000 + 5];
int num[120000 / 340 + 5], mn[120000 / 340 + 5], mnnum[120000 / 340 + 5],
    tag[120000 / 340 + 5], mntag[120000 / 340 + 5], tms[120000 / 340 + 5];
int A[340 + 5], B[340 + 5], Anum, Bnum, rk[120000 / 340 + 5][340 + 5],
    cc[120000 / 340 + 5];
struct ad {
  int l, r, x;
} s[120000 * 2 + 5];
vector<pair<int, int> > v[120000 + 5];
void Rebuild(int x, int l, int r, int ad) {
  Anum = Bnum = 0;
  int L = (x - 1) * 340 + 1, R = min(n, x * 340);
  for (int i = L; i <= R; ++i) {
    int add = (b[i] + mntag[x]) ? 0 : tms[x];
    Tag[i] += add;
    num[x] += add;
    b[i] += tag[x];
    if (i >= l && i <= r && !(b[i] = b[i] + ad)) ++Tag[i], ++num[x];
  }
  tag[x] = 0;
  mntag[x] = 1e9;
  tms[x] = 0;
  for (int i = 1; i <= cc[x]; ++i)
    if (rk[x][i] >= l && rk[x][i] <= r)
      A[++Anum] = rk[x][i];
    else
      B[++Bnum] = rk[x][i];
  cc[x] = 0;
  for (int i = 1, j = 1; i <= Anum || j <= Bnum;)
    if (i <= Anum && (j > Bnum || b[A[i]] < b[B[j]]))
      rk[x][++cc[x]] = A[i++];
    else
      rk[x][++cc[x]] = B[j++];
  mn[x] = b[rk[x][1]];
  mnnum[x] = 0;
  for (int j = 1; j <= cc[x]; ++j)
    if (b[rk[x][j]] == mn[x])
      ++mnnum[x];
    else
      break;
}
void Modify(int l, int r, int x) {
  for (int i = block[l] + 1; i < block[r]; ++i) {
    tag[i] += x;
    if (tag[i] < mntag[i])
      mntag[i] = tag[i], tms[i] = 1;
    else if (tag[i] == mntag[i])
      ++tms[i];
  }
  Rebuild(block[l], l, r, x);
  if (block[l] != block[r]) Rebuild(block[r], l, r, x);
}
long long Query(int l, int r) {
  long long res = 0;
  for (int i = block[l] + 1; i < block[r]; ++i)
    res += num[i] + ((mn[i] + mntag[i]) ? 0 : mnnum[i] * tms[i]);
  for (int i = l; block[i] == block[l] && i <= r; ++i)
    res += Tag[i] + ((b[i] + mntag[block[i]]) ? 0 : tms[block[i]]);
  if (block[l] != block[r])
    for (int i = r; block[i] == block[r]; --i)
      res += Tag[i] + ((b[i] + mntag[block[i]]) ? 0 : tms[block[i]]);
  return res;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    a[i] = read(), block[i] = (i - 1) / 340 + 1, b[i] = i;
  for (int i = 1; i <= block[n]; ++i) {
    for (int j = (i - 1) * 340 + 1; block[j] == i; ++j) rk[i][++cc[i]] = j;
    mn[i] = (i - 1) * 340 + 1, mnnum[i] = 1, mntag[i] = 1e9;
  }
  m = read();
  for (int i = 1; i <= m; ++i) {
    int l = read(), r = read();
    v[r].push_back(make_pair(l, i));
  }
  for (int i = 1; i <= n; ++i) {
    cnt = 0;
    while (top && a[i] <= a[q[top]])
      Modify(q[top - 1] + 1, q[top], a[q[top]]), --top;
    s[++cnt] = (ad){q[top] + 1, i, -a[i]};
    q[++top] = i;
    while (Top && a[i] >= a[Q[Top]])
      s[++cnt] = (ad){Q[Top - 1] + 1, Q[Top], -a[Q[Top]]}, --Top;
    Modify(Q[Top] + 1, i, a[i]);
    Q[++Top] = i;
    for (int j = 1; j <= cnt; ++j) Modify(s[j].l, s[j].r, s[j].x);
    Modify(1, n, -1);
    for (int j = 0; j < v[i].size(); ++j)
      Ans[v[i][j].second] = Query(v[i][j].first, i);
  }
  for (int i = 1; i <= m; ++i) printf("%lld\n", Ans[i]);
  return 0;
}

### Prompt

Generate 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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long long Ans[120000 + 5];
int n, m, a[120000 + 5], b[120000 + 5], q[120000 + 5], top, Q[120000 + 5], Top,
    cnt, block[120000 + 5], Tag[120000 + 5];
int num[120000 / 340 + 5], mn[120000 / 340 + 5], mnnum[120000 / 340 + 5],
    tag[120000 / 340 + 5], mntag[120000 / 340 + 5], tms[120000 / 340 + 5];
int A[340 + 5], B[340 + 5], Anum, Bnum, rk[120000 / 340 + 5][340 + 5],
    cc[120000 / 340 + 5];
struct ad {
  int l, r, x;
} s[120000 * 2 + 5];
vector<pair<int, int> > v[120000 + 5];
void Rebuild(int x, int l, int r, int ad) {
  Anum = Bnum = 0;
  int L = (x - 1) * 340 + 1, R = min(n, x * 340);
  for (int i = L; i <= R; ++i) {
    int add = (b[i] + mntag[x]) ? 0 : tms[x];
    Tag[i] += add;
    num[x] += add;
    b[i] += tag[x];
    if (i >= l && i <= r && !(b[i] = b[i] + ad)) ++Tag[i], ++num[x];
  }
  tag[x] = 0;
  mntag[x] = 1e9;
  tms[x] = 0;
  for (int i = 1; i <= cc[x]; ++i)
    if (rk[x][i] >= l && rk[x][i] <= r)
      A[++Anum] = rk[x][i];
    else
      B[++Bnum] = rk[x][i];
  cc[x] = 0;
  for (int i = 1, j = 1; i <= Anum || j <= Bnum;)
    if (i <= Anum && (j > Bnum || b[A[i]] < b[B[j]]))
      rk[x][++cc[x]] = A[i++];
    else
      rk[x][++cc[x]] = B[j++];
  mn[x] = b[rk[x][1]];
  mnnum[x] = 0;
  for (int j = 1; j <= cc[x]; ++j)
    if (b[rk[x][j]] == mn[x])
      ++mnnum[x];
    else
      break;
}
void Modify(int l, int r, int x) {
  for (int i = block[l] + 1; i < block[r]; ++i) {
    tag[i] += x;
    if (tag[i] < mntag[i])
      mntag[i] = tag[i], tms[i] = 1;
    else if (tag[i] == mntag[i])
      ++tms[i];
  }
  Rebuild(block[l], l, r, x);
  if (block[l] != block[r]) Rebuild(block[r], l, r, x);
}
long long Query(int l, int r) {
  long long res = 0;
  for (int i = block[l] + 1; i < block[r]; ++i)
    res += num[i] + ((mn[i] + mntag[i]) ? 0 : mnnum[i] * tms[i]);
  for (int i = l; block[i] == block[l] && i <= r; ++i)
    res += Tag[i] + ((b[i] + mntag[block[i]]) ? 0 : tms[block[i]]);
  if (block[l] != block[r])
    for (int i = r; block[i] == block[r]; --i)
      res += Tag[i] + ((b[i] + mntag[block[i]]) ? 0 : tms[block[i]]);
  return res;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i)
    a[i] = read(), block[i] = (i - 1) / 340 + 1, b[i] = i;
  for (int i = 1; i <= block[n]; ++i) {
    for (int j = (i - 1) * 340 + 1; block[j] == i; ++j) rk[i][++cc[i]] = j;
    mn[i] = (i - 1) * 340 + 1, mnnum[i] = 1, mntag[i] = 1e9;
  }
  m = read();
  for (int i = 1; i <= m; ++i) {
    int l = read(), r = read();
    v[r].push_back(make_pair(l, i));
  }
  for (int i = 1; i <= n; ++i) {
    cnt = 0;
    while (top && a[i] <= a[q[top]])
      Modify(q[top - 1] + 1, q[top], a[q[top]]), --top;
    s[++cnt] = (ad){q[top] + 1, i, -a[i]};
    q[++top] = i;
    while (Top && a[i] >= a[Q[Top]])
      s[++cnt] = (ad){Q[Top - 1] + 1, Q[Top], -a[Q[Top]]}, --Top;
    Modify(Q[Top] + 1, i, a[i]);
    Q[++Top] = i;
    for (int j = 1; j <= cnt; ++j) Modify(s[j].l, s[j].r, s[j].x);
    Modify(1, n, -1);
    for (int j = 0; j < v[i].size(); ++j)
      Ans[v[i][j].second] = Query(v[i][j].first, i);
  }
  for (int i = 1; i <= m; ++i) printf("%lld\n", Ans[i]);
  return 0;
}

```