#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<pair<int, int> > qs[120105];
int p[120105];
long long mi[120105 * 4], mic[120105 * 4], cnt[120105 * 4], lz[120105 * 4];
long long ans[120105 * 4];
void Up(int rt, int l, int r) {
  mi[rt] = min(mi[(rt << 1)], mi[(rt << 1 | 1)]);
  ans[rt] = ans[(rt << 1)] + ans[(rt << 1 | 1)];
  mic[rt] = 0;
  if (mi[rt] == mi[(rt << 1)]) mic[rt] += mic[(rt << 1)];
  if (mi[rt] == mi[(rt << 1 | 1)]) mic[rt] += mic[(rt << 1 | 1)];
}
void Down(int rt, int l, int r) {
  if (lz[rt] != 0) {
    lz[(rt << 1)] += lz[rt];
    mi[(rt << 1)] += lz[rt];
    lz[(rt << 1 | 1)] += lz[rt];
    mi[(rt << 1 | 1)] += lz[rt];
    lz[rt] = 0;
  }
  if (cnt[rt] != 0) {
    if (mi[rt] == mi[(rt << 1)]) {
      ans[(rt << 1)] += (long long)cnt[rt] * mic[(rt << 1)];
      cnt[(rt << 1)] += cnt[rt];
    }
    if (mi[rt] == mi[(rt << 1 | 1)]) {
      ans[(rt << 1 | 1)] += (long long)cnt[rt] * mic[(rt << 1 | 1)];
      cnt[(rt << 1 | 1)] += cnt[rt];
    }
    cnt[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  if (l == r) {
    mi[rt] = l;
    mic[rt] = 1;
    return;
  }
  int mid = (l + r) / 2;
  build((rt << 1), l, mid);
  build((rt << 1 | 1), mid + 1, r);
  Up(rt, l, r);
}
void upt(int rt, int l, int r, int L, int R, int val) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) {
    mi[rt] += val;
    lz[rt] += val;
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, val);
  upt((rt << 1 | 1), mid + 1, r, L, R, val);
  Up(rt, l, r);
}
long long qy(int rt, int l, int r, int L, int R) {
  if (R < l || r < L) return 0;
  if (L <= l && r <= R) {
    return ans[rt];
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  return qy((rt << 1), l, mid, L, R) + qy((rt << 1 | 1), mid + 1, r, L, R);
}
vector<int> maxQ, minQ;
long long Ans[120105];
void fmain(int ID) {
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) scanf("%d", p + i);
  scanf("%d", &m);
  build(1, 1, n);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int l, r;
    scanf("%d%d", &l, &r);
    qs[r].push_back({l, i});
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    upt(1, 1, n, 1, n, -1);
    while (!maxQ.empty() && p[maxQ.back()] < p[i]) {
      int lst = maxQ.size() == 1 ? 0 : maxQ[maxQ.size() - 2];
      upt(1, 1, n, lst + 1, maxQ.back(), p[i] - p[maxQ.back()]);
      maxQ.pop_back();
    }
    maxQ.push_back(i);
    while (!minQ.empty() && p[minQ.back()] > p[i]) {
      int lst = minQ.size() == 1 ? 0 : minQ[minQ.size() - 2];
      upt(1, 1, n, lst + 1, minQ.back(), p[minQ.back()] - p[i]);
      minQ.pop_back();
    }
    minQ.push_back(i);
    cnt[1]++;
    ans[1] += mic[1];
    for (auto p : qs[i]) {
      Ans[p.second] += qy(1, 1, n, p.first, i);
    }
  }
  for (int(i) = 1; (i) <= (int)(m); (i)++) printf("%lld\n", Ans[i]);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### Prompt

Develop a solution in Cpp 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;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<pair<int, int> > qs[120105];
int p[120105];
long long mi[120105 * 4], mic[120105 * 4], cnt[120105 * 4], lz[120105 * 4];
long long ans[120105 * 4];
void Up(int rt, int l, int r) {
  mi[rt] = min(mi[(rt << 1)], mi[(rt << 1 | 1)]);
  ans[rt] = ans[(rt << 1)] + ans[(rt << 1 | 1)];
  mic[rt] = 0;
  if (mi[rt] == mi[(rt << 1)]) mic[rt] += mic[(rt << 1)];
  if (mi[rt] == mi[(rt << 1 | 1)]) mic[rt] += mic[(rt << 1 | 1)];
}
void Down(int rt, int l, int r) {
  if (lz[rt] != 0) {
    lz[(rt << 1)] += lz[rt];
    mi[(rt << 1)] += lz[rt];
    lz[(rt << 1 | 1)] += lz[rt];
    mi[(rt << 1 | 1)] += lz[rt];
    lz[rt] = 0;
  }
  if (cnt[rt] != 0) {
    if (mi[rt] == mi[(rt << 1)]) {
      ans[(rt << 1)] += (long long)cnt[rt] * mic[(rt << 1)];
      cnt[(rt << 1)] += cnt[rt];
    }
    if (mi[rt] == mi[(rt << 1 | 1)]) {
      ans[(rt << 1 | 1)] += (long long)cnt[rt] * mic[(rt << 1 | 1)];
      cnt[(rt << 1 | 1)] += cnt[rt];
    }
    cnt[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  if (l == r) {
    mi[rt] = l;
    mic[rt] = 1;
    return;
  }
  int mid = (l + r) / 2;
  build((rt << 1), l, mid);
  build((rt << 1 | 1), mid + 1, r);
  Up(rt, l, r);
}
void upt(int rt, int l, int r, int L, int R, int val) {
  if (R < l || r < L) return;
  if (L <= l && r <= R) {
    mi[rt] += val;
    lz[rt] += val;
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, val);
  upt((rt << 1 | 1), mid + 1, r, L, R, val);
  Up(rt, l, r);
}
long long qy(int rt, int l, int r, int L, int R) {
  if (R < l || r < L) return 0;
  if (L <= l && r <= R) {
    return ans[rt];
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  return qy((rt << 1), l, mid, L, R) + qy((rt << 1 | 1), mid + 1, r, L, R);
}
vector<int> maxQ, minQ;
long long Ans[120105];
void fmain(int ID) {
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) scanf("%d", p + i);
  scanf("%d", &m);
  build(1, 1, n);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int l, r;
    scanf("%d%d", &l, &r);
    qs[r].push_back({l, i});
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    upt(1, 1, n, 1, n, -1);
    while (!maxQ.empty() && p[maxQ.back()] < p[i]) {
      int lst = maxQ.size() == 1 ? 0 : maxQ[maxQ.size() - 2];
      upt(1, 1, n, lst + 1, maxQ.back(), p[i] - p[maxQ.back()]);
      maxQ.pop_back();
    }
    maxQ.push_back(i);
    while (!minQ.empty() && p[minQ.back()] > p[i]) {
      int lst = minQ.size() == 1 ? 0 : minQ[minQ.size() - 2];
      upt(1, 1, n, lst + 1, minQ.back(), p[minQ.back()] - p[i]);
      minQ.pop_back();
    }
    minQ.push_back(i);
    cnt[1]++;
    ans[1] += mic[1];
    for (auto p : qs[i]) {
      Ans[p.second] += qy(1, 1, n, p.first, i);
    }
  }
  for (int(i) = 1; (i) <= (int)(m); (i)++) printf("%lld\n", Ans[i]);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```