#include <bits/stdc++.h>
using namespace std;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 1.2e5 + 5;
const int INF = 1e9;
int n, q;
int a[N];
long long ans[N];
struct QUERY {
  int l, r, id;
  QUERY(const int l_ = 0, const int r_ = 0, const int id_ = 0) {
    l = l_;
    r = r_;
    id = id_;
  }
  friend bool operator<(QUERY a, QUERY b) { return a.id < b.id; }
};
set<QUERY> s[N];
struct node {
  int l, r;
  int mv, tot, tim, ad;
  long long sum;
} tree[N * 2];
int rt, tot;
void build(int &now, int l, int r) {
  tree[now = ++tot].mv = INF;
  tree[now].tot = r - l + 1;
  tree[now].sum = tree[now].tim = tree[now].ad = 0;
  if (l == r) return;
  int mid = (l + r) / 2;
  build(tree[now].l, l, mid);
  build(tree[now].r, mid + 1, r);
}
void down(int now) {
  int l = tree[now].l, r = tree[now].r;
  if (tree[now].ad != 0) {
    int ad = tree[now].ad;
    tree[l].ad = tree[l].ad + ad;
    tree[l].mv = tree[l].mv + ad;
    tree[r].ad = tree[r].ad + ad;
    tree[r].mv = tree[r].mv + ad;
    tree[now].ad = 0;
  }
  if (tree[now].tim) {
    int tim = tree[now].tim;
    if (tree[l].mv == tree[now].mv) {
      tree[l].sum = tree[l].sum + 1ll * tim * tree[l].tot;
      tree[l].tim = tree[l].tim + tim;
    }
    if (tree[r].mv == tree[now].mv) {
      tree[r].sum = tree[r].sum + 1ll * tim * tree[r].tot;
      tree[r].tim = tree[r].tim + tim;
    }
    tree[now].tim = 0;
  }
}
void update(int now) {
  int l = tree[now].l, r = tree[now].r;
  tree[now].mv = tree[l].mv;
  tree[now].tot = tree[l].tot;
  if (tree[now].mv > tree[r].mv) tree[now].mv = tree[r].mv, tree[now].tot = 0;
  if (tree[now].mv == tree[r].mv) tree[now].tot = tree[now].tot + tree[r].tot;
  tree[now].sum = tree[l].sum + tree[r].sum;
}
void add(int now, int l, int r, int x, int y, int v) {
  if (x <= l && r <= y) {
    tree[now].mv = tree[now].mv + v;
    tree[now].ad = tree[now].ad + v;
    return;
  }
  down(now);
  int mid = (l + r) / 2;
  if (x <= mid) add(tree[now].l, l, mid, x, y, v);
  if (y > mid) add(tree[now].r, mid + 1, r, x, y, v);
  update(now);
}
void change(int now, int l, int r, int x, int v) {
  if (l == r) {
    tree[now].tot = 1;
    tree[now].mv = v;
    return;
  }
  down(now);
  int mid = (l + r) / 2;
  if (x <= mid)
    change(tree[now].l, l, mid, x, v);
  else
    change(tree[now].r, mid + 1, r, x, v);
  update(now);
}
void update() {
  tree[rt].sum = tree[rt].sum + tree[rt].tot;
  tree[rt].tim++;
}
long long query(int now, int l, int r, int x, int y) {
  if (x <= l && r <= y) return tree[now].sum;
  down(now);
  int mid = (l + r) / 2;
  long long ret = 0;
  if (x <= mid) ret = query(tree[now].l, l, mid, x, y);
  if (y > mid) ret = ret + query(tree[now].r, mid + 1, r, x, y);
  return ret;
}
struct Decreasing_Stack {
  int len, a[N], w[N];
  void init() { len = 0; }
  void pushback(int x, int p) {
    while (len && a[len] < x) {
      add(rt, 1, n, w[len - 1] + 1, w[len], -a[len]);
      len--;
    }
    add(rt, 1, n, w[len] + 1, p, x);
    a[++len] = x;
    w[len] = p;
  }
} Max, Min;
int main() {
  n = get();
  for (int i = 1; i <= n; i++) a[i] = get();
  q = get();
  for (int i = 1; i <= q; i++) {
    int l = get(), r = get();
    s[r].insert(QUERY(l, r, i));
  }
  Max.init();
  Min.init();
  build(rt, 1, n);
  for (int i = 1; i <= n; i++) {
    Max.pushback(a[i], i);
    Min.pushback(-a[i], i);
    add(rt, 1, n, 1, i, -1);
    change(rt, 1, n, i, 0);
    update();
    for (set<QUERY>::iterator h = s[i].begin(); h != s[i].end(); h++)
      ans[(*h).id] = query(rt, 1, n, (*h).l, (*h).r);
  }
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  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;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 1.2e5 + 5;
const int INF = 1e9;
int n, q;
int a[N];
long long ans[N];
struct QUERY {
  int l, r, id;
  QUERY(const int l_ = 0, const int r_ = 0, const int id_ = 0) {
    l = l_;
    r = r_;
    id = id_;
  }
  friend bool operator<(QUERY a, QUERY b) { return a.id < b.id; }
};
set<QUERY> s[N];
struct node {
  int l, r;
  int mv, tot, tim, ad;
  long long sum;
} tree[N * 2];
int rt, tot;
void build(int &now, int l, int r) {
  tree[now = ++tot].mv = INF;
  tree[now].tot = r - l + 1;
  tree[now].sum = tree[now].tim = tree[now].ad = 0;
  if (l == r) return;
  int mid = (l + r) / 2;
  build(tree[now].l, l, mid);
  build(tree[now].r, mid + 1, r);
}
void down(int now) {
  int l = tree[now].l, r = tree[now].r;
  if (tree[now].ad != 0) {
    int ad = tree[now].ad;
    tree[l].ad = tree[l].ad + ad;
    tree[l].mv = tree[l].mv + ad;
    tree[r].ad = tree[r].ad + ad;
    tree[r].mv = tree[r].mv + ad;
    tree[now].ad = 0;
  }
  if (tree[now].tim) {
    int tim = tree[now].tim;
    if (tree[l].mv == tree[now].mv) {
      tree[l].sum = tree[l].sum + 1ll * tim * tree[l].tot;
      tree[l].tim = tree[l].tim + tim;
    }
    if (tree[r].mv == tree[now].mv) {
      tree[r].sum = tree[r].sum + 1ll * tim * tree[r].tot;
      tree[r].tim = tree[r].tim + tim;
    }
    tree[now].tim = 0;
  }
}
void update(int now) {
  int l = tree[now].l, r = tree[now].r;
  tree[now].mv = tree[l].mv;
  tree[now].tot = tree[l].tot;
  if (tree[now].mv > tree[r].mv) tree[now].mv = tree[r].mv, tree[now].tot = 0;
  if (tree[now].mv == tree[r].mv) tree[now].tot = tree[now].tot + tree[r].tot;
  tree[now].sum = tree[l].sum + tree[r].sum;
}
void add(int now, int l, int r, int x, int y, int v) {
  if (x <= l && r <= y) {
    tree[now].mv = tree[now].mv + v;
    tree[now].ad = tree[now].ad + v;
    return;
  }
  down(now);
  int mid = (l + r) / 2;
  if (x <= mid) add(tree[now].l, l, mid, x, y, v);
  if (y > mid) add(tree[now].r, mid + 1, r, x, y, v);
  update(now);
}
void change(int now, int l, int r, int x, int v) {
  if (l == r) {
    tree[now].tot = 1;
    tree[now].mv = v;
    return;
  }
  down(now);
  int mid = (l + r) / 2;
  if (x <= mid)
    change(tree[now].l, l, mid, x, v);
  else
    change(tree[now].r, mid + 1, r, x, v);
  update(now);
}
void update() {
  tree[rt].sum = tree[rt].sum + tree[rt].tot;
  tree[rt].tim++;
}
long long query(int now, int l, int r, int x, int y) {
  if (x <= l && r <= y) return tree[now].sum;
  down(now);
  int mid = (l + r) / 2;
  long long ret = 0;
  if (x <= mid) ret = query(tree[now].l, l, mid, x, y);
  if (y > mid) ret = ret + query(tree[now].r, mid + 1, r, x, y);
  return ret;
}
struct Decreasing_Stack {
  int len, a[N], w[N];
  void init() { len = 0; }
  void pushback(int x, int p) {
    while (len && a[len] < x) {
      add(rt, 1, n, w[len - 1] + 1, w[len], -a[len]);
      len--;
    }
    add(rt, 1, n, w[len] + 1, p, x);
    a[++len] = x;
    w[len] = p;
  }
} Max, Min;
int main() {
  n = get();
  for (int i = 1; i <= n; i++) a[i] = get();
  q = get();
  for (int i = 1; i <= q; i++) {
    int l = get(), r = get();
    s[r].insert(QUERY(l, r, i));
  }
  Max.init();
  Min.init();
  build(rt, 1, n);
  for (int i = 1; i <= n; i++) {
    Max.pushback(a[i], i);
    Min.pushback(-a[i], i);
    add(rt, 1, n, 1, i, -1);
    change(rt, 1, n, i, 0);
    update();
    for (set<QUERY>::iterator h = s[i].begin(); h != s[i].end(); h++)
      ans[(*h).id] = query(rt, 1, n, (*h).l, (*h).r);
  }
  for (int i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}

```