#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 200111;
const int maxh = 18;
struct SGT {
  struct node {
    int sum;
    long long hsum, lz;
    void addlz(int LZ) {
      lz += LZ;
      hsum += 1ll * LZ * sum;
    }
  } a[maxn * 4];
  void update(int p) {
    a[p].sum = a[p << 1].sum + a[p << 1 | 1].sum;
    a[p].hsum = a[p << 1].hsum + a[p << 1 | 1].hsum;
  }
  void pushdown(int p) {
    if (a[p].lz != 0) {
      a[p << 1].addlz(a[p].lz);
      a[p << 1 | 1].addlz(a[p].lz);
      a[p].lz = 0;
    }
  }
  void modify(int x, int v, int l, int r, int p) {
    if (l == r) {
      a[p].sum = v;
      return;
    }
    pushdown(p);
    int m = l + r >> 1;
    if (x <= m)
      modify(x, v, l, m, p << 1);
    else
      modify(x, v, m + 1, r, p << 1 | 1);
    update(p);
  }
  void add(int x, int y, int l, int r, int p) {
    if (x <= l && r <= y) {
      a[p].addlz(1);
      return;
    }
    if (y < l || r < x) return;
    pushdown(p);
    int m = l + r >> 1;
    add(x, y, l, m, p << 1);
    add(x, y, m + 1, r, p << 1 | 1);
    update(p);
  }
  long long query(int x, int y, int l, int r, int p) {
    if (x <= l && r <= y) return a[p].hsum;
    if (y < l || r < x) return 0;
    pushdown(p);
    int m = l + r >> 1;
    return query(x, y, l, m, p << 1) + query(x, y, m + 1, r, p << 1 | 1);
  }
} sgt;
int lg2[maxn];
struct STtable {
  int tab[maxh][maxn];
  int C;
  void init(int a[], int n, int c) {
    C = c;
    for (int i = 0; i <= n; i++) tab[0][i] = a[i] * c;
    for (int i = 1; i < maxh; i++) {
      for (int j = 0; j <= n - (1 << i) + 1; j++) {
        tab[i][j] = max(tab[i - 1][j], tab[i - 1][j + (1 << i - 1)]);
      }
    }
  }
  int query(int l, int r) {
    int t = lg2[r - l + 1];
    return max(tab[t][l], tab[t][r - (1 << t) + 1]) * C;
  }
} STb_mn, STb_mx;
int n, a[maxn], b[maxn];
int gl[maxn], gr[maxn];
int L[maxn], R[maxn];
int f[maxn];
int gf(int x) { return f[x] == x ? x : f[x] = gf(f[x]); }
long long ANS[maxn];
vector<pair<int, int> > qry[maxn];
void solve() {
  static int st[maxn], stn;
  for (int i = 1; i <= n; i++) f[i] = i;
  stn = 0;
  st[0] = 0;
  for (int i = 2; i <= n; i++) {
    if (gr[i - 1] > i) st[++stn] = i - 1;
    sgt.modify(i - 1, 1, 1, n, 1);
    if (gl[i - 1] < i - 1) {
      for (int j = gf(i - 1); j > gl[i - 1]; j = gf(j)) {
        f[j] = gf(j - 1);
        sgt.modify(j, 0, 1, n, 1);
      }
    }
    while (stn > 0 && gr[st[stn]] <= i) stn--;
    sgt.add(st[stn] + 1, i - 1, 1, n, 1);
    for (int j = 0; j < qry[i].size(); j++) {
      ANS[qry[i][j].second] += sgt.query(qry[i][j].first, i, 1, n, 1);
    }
  }
}
int main() {
  for (int i = 2; i < maxn; i++) lg2[i] = lg2[i >> 1] + 1;
  n = getnum();
  for (int i = 1; i <= n; i++) a[i] = getnum(), b[a[i]] = i;
  STb_mn.init(b, n, -1);
  STb_mx.init(b, n, 1);
  for (int i = 1; i < n; i++) {
    int l = a[i], r = a[i + 1];
    if (l > r) swap(l, r);
    gl[i] = STb_mn.query(l, r);
    gr[i] = STb_mx.query(l, r);
  }
  int q;
  q = getnum();
  for (int i = 0; i < q; i++) {
    int l, r;
    l = getnum(), r = getnum();
    qry[r].push_back(make_pair(l, i));
    ANS[i] += r - l + 1;
  }
  solve();
  for (int i = 0; i < q; i++) putnum(ANS[i]), putchar('\n');
  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;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
long long qpow(long long x, long long k) {
  return k == 0 ? 1
                : 1ll * qpow(1ll * x * x % mod, k >> 1) * (k & 1 ? x : 1) % mod;
}
const int maxn = 200111;
const int maxh = 18;
struct SGT {
  struct node {
    int sum;
    long long hsum, lz;
    void addlz(int LZ) {
      lz += LZ;
      hsum += 1ll * LZ * sum;
    }
  } a[maxn * 4];
  void update(int p) {
    a[p].sum = a[p << 1].sum + a[p << 1 | 1].sum;
    a[p].hsum = a[p << 1].hsum + a[p << 1 | 1].hsum;
  }
  void pushdown(int p) {
    if (a[p].lz != 0) {
      a[p << 1].addlz(a[p].lz);
      a[p << 1 | 1].addlz(a[p].lz);
      a[p].lz = 0;
    }
  }
  void modify(int x, int v, int l, int r, int p) {
    if (l == r) {
      a[p].sum = v;
      return;
    }
    pushdown(p);
    int m = l + r >> 1;
    if (x <= m)
      modify(x, v, l, m, p << 1);
    else
      modify(x, v, m + 1, r, p << 1 | 1);
    update(p);
  }
  void add(int x, int y, int l, int r, int p) {
    if (x <= l && r <= y) {
      a[p].addlz(1);
      return;
    }
    if (y < l || r < x) return;
    pushdown(p);
    int m = l + r >> 1;
    add(x, y, l, m, p << 1);
    add(x, y, m + 1, r, p << 1 | 1);
    update(p);
  }
  long long query(int x, int y, int l, int r, int p) {
    if (x <= l && r <= y) return a[p].hsum;
    if (y < l || r < x) return 0;
    pushdown(p);
    int m = l + r >> 1;
    return query(x, y, l, m, p << 1) + query(x, y, m + 1, r, p << 1 | 1);
  }
} sgt;
int lg2[maxn];
struct STtable {
  int tab[maxh][maxn];
  int C;
  void init(int a[], int n, int c) {
    C = c;
    for (int i = 0; i <= n; i++) tab[0][i] = a[i] * c;
    for (int i = 1; i < maxh; i++) {
      for (int j = 0; j <= n - (1 << i) + 1; j++) {
        tab[i][j] = max(tab[i - 1][j], tab[i - 1][j + (1 << i - 1)]);
      }
    }
  }
  int query(int l, int r) {
    int t = lg2[r - l + 1];
    return max(tab[t][l], tab[t][r - (1 << t) + 1]) * C;
  }
} STb_mn, STb_mx;
int n, a[maxn], b[maxn];
int gl[maxn], gr[maxn];
int L[maxn], R[maxn];
int f[maxn];
int gf(int x) { return f[x] == x ? x : f[x] = gf(f[x]); }
long long ANS[maxn];
vector<pair<int, int> > qry[maxn];
void solve() {
  static int st[maxn], stn;
  for (int i = 1; i <= n; i++) f[i] = i;
  stn = 0;
  st[0] = 0;
  for (int i = 2; i <= n; i++) {
    if (gr[i - 1] > i) st[++stn] = i - 1;
    sgt.modify(i - 1, 1, 1, n, 1);
    if (gl[i - 1] < i - 1) {
      for (int j = gf(i - 1); j > gl[i - 1]; j = gf(j)) {
        f[j] = gf(j - 1);
        sgt.modify(j, 0, 1, n, 1);
      }
    }
    while (stn > 0 && gr[st[stn]] <= i) stn--;
    sgt.add(st[stn] + 1, i - 1, 1, n, 1);
    for (int j = 0; j < qry[i].size(); j++) {
      ANS[qry[i][j].second] += sgt.query(qry[i][j].first, i, 1, n, 1);
    }
  }
}
int main() {
  for (int i = 2; i < maxn; i++) lg2[i] = lg2[i >> 1] + 1;
  n = getnum();
  for (int i = 1; i <= n; i++) a[i] = getnum(), b[a[i]] = i;
  STb_mn.init(b, n, -1);
  STb_mx.init(b, n, 1);
  for (int i = 1; i < n; i++) {
    int l = a[i], r = a[i + 1];
    if (l > r) swap(l, r);
    gl[i] = STb_mn.query(l, r);
    gr[i] = STb_mx.query(l, r);
  }
  int q;
  q = getnum();
  for (int i = 0; i < q; i++) {
    int l, r;
    l = getnum(), r = getnum();
    qry[r].push_back(make_pair(l, i));
    ANS[i] += r - l + 1;
  }
  solve();
  for (int i = 0; i < q; i++) putnum(ANS[i]), putchar('\n');
  return 0;
}

```