#include <bits/stdc++.h>
using namespace std;
const long long N = 200000;
long long n, a[N], Log[N], Pow[N], Q, p[N], stkmax[N], stkmin[N], top1, top2;
long long qz[N], ans[N];
struct Que {
  long long l, r, id;
  bool operator<(const Que &x) const { return r < x.r; }
} q[N];
struct node {
  long long sum, tag, cnt, ans, anstag;
} t[N << 2];
struct st {
  long long Min, Max;
} st[N][20];
void pushdown(long long i) {
  long long ls = i << 1, rs = ls | 1;
  if (t[i].tag != 0) {
    t[ls].tag += t[i].tag;
    t[rs].tag += t[i].tag;
    t[ls].sum += t[i].tag;
    t[rs].sum += t[i].tag;
    t[i].tag = 0;
  }
  if (t[i].anstag != 0) {
    if (t[ls].sum == t[i].sum)
      t[ls].ans += t[ls].cnt * t[i].anstag, t[ls].anstag += t[i].anstag;
    if (t[rs].sum == t[i].sum)
      t[rs].ans += t[rs].cnt * t[i].anstag, t[rs].anstag += t[i].anstag;
    t[i].anstag = 0;
  }
}
void pushup(long long i) {
  long long ls = i << 1, rs = ls | 1;
  t[i].ans = t[ls].ans + t[rs].ans;
  if (t[ls].sum == t[rs].sum) {
    t[i].sum = t[ls].sum;
    t[i].cnt = t[ls].cnt + t[rs].cnt;
    return;
  }
  if (t[ls].sum > t[rs].sum) {
    t[i].sum = t[rs].sum;
    t[i].cnt = t[rs].cnt;
    return;
  }
  if (t[ls].sum < t[rs].sum) {
    t[i].sum = t[ls].sum;
    t[i].cnt = t[ls].cnt;
    return;
  }
}
void build(long long i, long long l, long long r) {
  if (l == r) {
    t[i].sum = l;
    t[i].cnt = 1;
    return;
  }
  long long mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  pushup(i);
}
void add(long long i, long long l, long long r, long long x, long long y,
         long long z) {
  if (l >= x && r <= y) {
    t[i].tag += z;
    t[i].sum += z;
    return;
  }
  long long mid = (l + r) >> 1;
  pushdown(i);
  if (mid >= x) add(i << 1, l, mid, x, y, z);
  if (mid < y) add(i << 1 | 1, mid + 1, r, x, y, z);
  pushup(i);
}
long long query(long long i, long long l, long long r, long long x,
                long long y) {
  if (l >= x && r <= y) return t[i].ans;
  long long mid = (l + r) >> 1, ans = 0;
  pushdown(i);
  if (mid >= x) ans += query(i << 1, l, mid, x, y);
  if (mid < y) ans += query(i << 1 | 1, mid + 1, r, x, y);
  pushup(i);
  return ans;
}
long long getmin(long long l, long long r) {
  long long h = Log[r - l + 1];
  return min(st[l][h].Min, st[r - Pow[h] + 1][h].Min);
}
long long getmax(long long l, long long r) {
  long long h = Log[r - l + 1];
  return max(st[l][h].Max, st[r - Pow[h] + 1][h].Max);
}
void write(long long i, long long l, long long r) {
  pushdown(i);
  cout << i << ' ' << l << ' ' << r << " ans=" << t[i].ans
       << " anstag=" << t[i].anstag << " sum=" << t[i].sum
       << " cnt=" << t[i].cnt << " tag=" << t[i].tag << endl;
  if (l == r) return;
  long long mid = (l + r) >> 1;
  write(i << 1, l, mid);
  write(i << 1 | 1, mid + 1, r);
  pushup(i);
}
signed main() {
  scanf("%lld", &n);
  build(1, 1, n);
  for (long long i = 1; i <= n; i++)
    scanf("%lld", &p[i]), st[i][0] = {p[i], p[i]};
  for (long long i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
  Pow[0] = 1;
  for (long long i = 1; i <= Log[n]; i++) Pow[i] = Pow[i - 1] << 1;
  for (long long i = 1; i <= Log[n]; i++)
    for (long long j = 1; j <= n - Pow[i] + 1; j++)
      st[j][i].Min = min(st[j][i - 1].Min, st[j + Pow[i - 1]][i - 1].Min),
      st[j][i].Max = max(st[j][i - 1].Max, st[j + Pow[i - 1]][i - 1].Max);
  scanf("%lld", &Q);
  for (long long i = 1; i <= Q; i++) {
    scanf("%lld%lld", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + Q + 1);
  long long now = 1;
  for (long long i = 1; i <= n; i++) {
    while (top1 && p[stkmax[top1]] < p[i]) {
      add(1, 1, n, stkmax[top1 - 1] + 1, stkmax[top1], p[i] - p[stkmax[top1]]);
      --top1;
    }
    stkmax[++top1] = i;
    while (top2 && p[stkmin[top2]] > p[i]) {
      add(1, 1, n, stkmin[top2 - 1] + 1, stkmin[top2], p[stkmin[top2]] - p[i]);
      --top2;
    }
    stkmin[++top2] = i;
    add(1, 1, n, 1, n, -1);
    t[1].ans += t[1].cnt;
    t[1].anstag++;
    while (i == q[now].r)
      ans[q[now].id] = query(1, 1, n, q[now].l, q[now].r), ++now;
  }
  for (long long i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}

### Prompt

Please provide a cpp coded solution 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 long long N = 200000;
long long n, a[N], Log[N], Pow[N], Q, p[N], stkmax[N], stkmin[N], top1, top2;
long long qz[N], ans[N];
struct Que {
  long long l, r, id;
  bool operator<(const Que &x) const { return r < x.r; }
} q[N];
struct node {
  long long sum, tag, cnt, ans, anstag;
} t[N << 2];
struct st {
  long long Min, Max;
} st[N][20];
void pushdown(long long i) {
  long long ls = i << 1, rs = ls | 1;
  if (t[i].tag != 0) {
    t[ls].tag += t[i].tag;
    t[rs].tag += t[i].tag;
    t[ls].sum += t[i].tag;
    t[rs].sum += t[i].tag;
    t[i].tag = 0;
  }
  if (t[i].anstag != 0) {
    if (t[ls].sum == t[i].sum)
      t[ls].ans += t[ls].cnt * t[i].anstag, t[ls].anstag += t[i].anstag;
    if (t[rs].sum == t[i].sum)
      t[rs].ans += t[rs].cnt * t[i].anstag, t[rs].anstag += t[i].anstag;
    t[i].anstag = 0;
  }
}
void pushup(long long i) {
  long long ls = i << 1, rs = ls | 1;
  t[i].ans = t[ls].ans + t[rs].ans;
  if (t[ls].sum == t[rs].sum) {
    t[i].sum = t[ls].sum;
    t[i].cnt = t[ls].cnt + t[rs].cnt;
    return;
  }
  if (t[ls].sum > t[rs].sum) {
    t[i].sum = t[rs].sum;
    t[i].cnt = t[rs].cnt;
    return;
  }
  if (t[ls].sum < t[rs].sum) {
    t[i].sum = t[ls].sum;
    t[i].cnt = t[ls].cnt;
    return;
  }
}
void build(long long i, long long l, long long r) {
  if (l == r) {
    t[i].sum = l;
    t[i].cnt = 1;
    return;
  }
  long long mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  pushup(i);
}
void add(long long i, long long l, long long r, long long x, long long y,
         long long z) {
  if (l >= x && r <= y) {
    t[i].tag += z;
    t[i].sum += z;
    return;
  }
  long long mid = (l + r) >> 1;
  pushdown(i);
  if (mid >= x) add(i << 1, l, mid, x, y, z);
  if (mid < y) add(i << 1 | 1, mid + 1, r, x, y, z);
  pushup(i);
}
long long query(long long i, long long l, long long r, long long x,
                long long y) {
  if (l >= x && r <= y) return t[i].ans;
  long long mid = (l + r) >> 1, ans = 0;
  pushdown(i);
  if (mid >= x) ans += query(i << 1, l, mid, x, y);
  if (mid < y) ans += query(i << 1 | 1, mid + 1, r, x, y);
  pushup(i);
  return ans;
}
long long getmin(long long l, long long r) {
  long long h = Log[r - l + 1];
  return min(st[l][h].Min, st[r - Pow[h] + 1][h].Min);
}
long long getmax(long long l, long long r) {
  long long h = Log[r - l + 1];
  return max(st[l][h].Max, st[r - Pow[h] + 1][h].Max);
}
void write(long long i, long long l, long long r) {
  pushdown(i);
  cout << i << ' ' << l << ' ' << r << " ans=" << t[i].ans
       << " anstag=" << t[i].anstag << " sum=" << t[i].sum
       << " cnt=" << t[i].cnt << " tag=" << t[i].tag << endl;
  if (l == r) return;
  long long mid = (l + r) >> 1;
  write(i << 1, l, mid);
  write(i << 1 | 1, mid + 1, r);
  pushup(i);
}
signed main() {
  scanf("%lld", &n);
  build(1, 1, n);
  for (long long i = 1; i <= n; i++)
    scanf("%lld", &p[i]), st[i][0] = {p[i], p[i]};
  for (long long i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
  Pow[0] = 1;
  for (long long i = 1; i <= Log[n]; i++) Pow[i] = Pow[i - 1] << 1;
  for (long long i = 1; i <= Log[n]; i++)
    for (long long j = 1; j <= n - Pow[i] + 1; j++)
      st[j][i].Min = min(st[j][i - 1].Min, st[j + Pow[i - 1]][i - 1].Min),
      st[j][i].Max = max(st[j][i - 1].Max, st[j + Pow[i - 1]][i - 1].Max);
  scanf("%lld", &Q);
  for (long long i = 1; i <= Q; i++) {
    scanf("%lld%lld", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + Q + 1);
  long long now = 1;
  for (long long i = 1; i <= n; i++) {
    while (top1 && p[stkmax[top1]] < p[i]) {
      add(1, 1, n, stkmax[top1 - 1] + 1, stkmax[top1], p[i] - p[stkmax[top1]]);
      --top1;
    }
    stkmax[++top1] = i;
    while (top2 && p[stkmin[top2]] > p[i]) {
      add(1, 1, n, stkmin[top2 - 1] + 1, stkmin[top2], p[stkmin[top2]] - p[i]);
      --top2;
    }
    stkmin[++top2] = i;
    add(1, 1, n, 1, n, -1);
    t[1].ans += t[1].cnt;
    t[1].anstag++;
    while (i == q[now].r)
      ans[q[now].id] = query(1, 1, n, q[now].l, q[now].r), ++now;
  }
  for (long long i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}

```