#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 998244353;
const long long maxn = 1.2e5 + 7;
const double pi = acos(-1.0);
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = (long long)a * a % M)
    if (b & 1) ret = (long long)ret * a % M;
  return ret;
}
struct node {
  int lazy, minimum, times, cnt;
  long long ans;
  node() {
    lazy = minimum = cnt = times = 0;
    ans = 0;
  }
} T[maxn << 2];
inline void update_value(int x, int k) {
  T[x].minimum += k;
  T[x].lazy += k;
}
inline void update_times(int x, int k) {
  T[x].times += k;
  T[x].ans += (long long)k * T[x].cnt;
}
inline void pushdown(int x) {
  if (T[x].lazy) {
    update_value(x << 1, T[x].lazy);
    update_value(x << 1 | 1, T[x].lazy);
    T[x].lazy = 0;
  }
  if (T[x].times) {
    if (T[x].minimum == T[x << 1].minimum) update_times(x << 1, T[x].times);
    if (T[x].minimum == T[x << 1 | 1].minimum)
      update_times(x << 1 | 1, T[x].times);
    T[x].times = 0;
  }
}
node merge(node A, node B) {
  node ret;
  ret.minimum = min(A.minimum, B.minimum);
  if (ret.minimum == A.minimum) ret.cnt += A.cnt;
  if (ret.minimum == B.minimum) ret.cnt += B.cnt;
  ret.ans = A.ans + B.ans;
  return ret;
}
void update(int x, int l, int r, int val, int L, int R) {
  if (l <= L && R <= r) {
    update_value(x, val);
    return;
  }
  int mid = (L + R) / 2;
  pushdown(x);
  if (l <= mid) update(x << 1, l, r, val, L, mid);
  if (mid < r) update(x << 1 | 1, l, r, val, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
void update(int x, int pos, int val, int L, int R) {
  if (L == R) {
    T[x].cnt += val;
    return;
  }
  int mid = (L + R) / 2;
  pushdown(x);
  if (pos <= mid) update(x << 1, pos, val, L, mid);
  if (mid < pos) update(x << 1 | 1, pos, val, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
long long query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return T[x].ans;
  long long ret = 0;
  int mid = (L + R) / 2;
  pushdown(x);
  if (l <= mid) ret += query(x << 1, l, r, L, mid);
  if (mid < r) ret += query(x << 1 | 1, l, r, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
  return ret;
}
int A[maxn];
long long ans[maxn];
int stack_max[maxn], top_max;
int stack_min[maxn], top_min;
vector<pair<int, int> > queries[maxn];
int TaskA() {
  int i, j, k;
  int n, q;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    queries[r].push_back(make_pair(l, i));
  }
  for (k = 1; k <= n; k++) {
    while (top_max && A[stack_max[top_max]] <= A[k]) {
      int pos = stack_max[top_max--];
      update(1, stack_max[top_max] + 1, pos, A[k] - A[pos], 1, n);
    }
    stack_max[++top_max] = k;
    while (top_min && -A[stack_min[top_min]] <= -A[k]) {
      int pos = stack_min[top_min--];
      update(1, stack_min[top_min] + 1, pos, -A[k] + A[pos], 1, n);
    }
    stack_min[++top_min] = k;
    update(1, k, 1, 1, n);
    update_times(1, 1);
    for (auto now : queries[k]) {
      int l = now.first, id = now.second, r = k;
      ans[id] = query(1, l, r, 1, n);
    }
    update(1, 1, k, -1, 1, n);
  }
  for (i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}
void initialize() {}
int main() {
  int startTime = clock();
  initialize();
  fprintf(stderr, "/--- initializeTime: %ld milliseconds ---/\n",
          clock() - startTime);
  int T = 1;
  startTime = clock();
  while (T--) TaskA();
  fprintf(stderr, "/--- computeTime: %ld milliseconds ---/\n",
          clock() - startTime);
}

### Prompt

In Cpp, your task is to solve 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 INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 998244353;
const long long maxn = 1.2e5 + 7;
const double pi = acos(-1.0);
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = (long long)a * a % M)
    if (b & 1) ret = (long long)ret * a % M;
  return ret;
}
struct node {
  int lazy, minimum, times, cnt;
  long long ans;
  node() {
    lazy = minimum = cnt = times = 0;
    ans = 0;
  }
} T[maxn << 2];
inline void update_value(int x, int k) {
  T[x].minimum += k;
  T[x].lazy += k;
}
inline void update_times(int x, int k) {
  T[x].times += k;
  T[x].ans += (long long)k * T[x].cnt;
}
inline void pushdown(int x) {
  if (T[x].lazy) {
    update_value(x << 1, T[x].lazy);
    update_value(x << 1 | 1, T[x].lazy);
    T[x].lazy = 0;
  }
  if (T[x].times) {
    if (T[x].minimum == T[x << 1].minimum) update_times(x << 1, T[x].times);
    if (T[x].minimum == T[x << 1 | 1].minimum)
      update_times(x << 1 | 1, T[x].times);
    T[x].times = 0;
  }
}
node merge(node A, node B) {
  node ret;
  ret.minimum = min(A.minimum, B.minimum);
  if (ret.minimum == A.minimum) ret.cnt += A.cnt;
  if (ret.minimum == B.minimum) ret.cnt += B.cnt;
  ret.ans = A.ans + B.ans;
  return ret;
}
void update(int x, int l, int r, int val, int L, int R) {
  if (l <= L && R <= r) {
    update_value(x, val);
    return;
  }
  int mid = (L + R) / 2;
  pushdown(x);
  if (l <= mid) update(x << 1, l, r, val, L, mid);
  if (mid < r) update(x << 1 | 1, l, r, val, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
void update(int x, int pos, int val, int L, int R) {
  if (L == R) {
    T[x].cnt += val;
    return;
  }
  int mid = (L + R) / 2;
  pushdown(x);
  if (pos <= mid) update(x << 1, pos, val, L, mid);
  if (mid < pos) update(x << 1 | 1, pos, val, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
long long query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return T[x].ans;
  long long ret = 0;
  int mid = (L + R) / 2;
  pushdown(x);
  if (l <= mid) ret += query(x << 1, l, r, L, mid);
  if (mid < r) ret += query(x << 1 | 1, l, r, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
  return ret;
}
int A[maxn];
long long ans[maxn];
int stack_max[maxn], top_max;
int stack_min[maxn], top_min;
vector<pair<int, int> > queries[maxn];
int TaskA() {
  int i, j, k;
  int n, q;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    queries[r].push_back(make_pair(l, i));
  }
  for (k = 1; k <= n; k++) {
    while (top_max && A[stack_max[top_max]] <= A[k]) {
      int pos = stack_max[top_max--];
      update(1, stack_max[top_max] + 1, pos, A[k] - A[pos], 1, n);
    }
    stack_max[++top_max] = k;
    while (top_min && -A[stack_min[top_min]] <= -A[k]) {
      int pos = stack_min[top_min--];
      update(1, stack_min[top_min] + 1, pos, -A[k] + A[pos], 1, n);
    }
    stack_min[++top_min] = k;
    update(1, k, 1, 1, n);
    update_times(1, 1);
    for (auto now : queries[k]) {
      int l = now.first, id = now.second, r = k;
      ans[id] = query(1, l, r, 1, n);
    }
    update(1, 1, k, -1, 1, n);
  }
  for (i = 1; i <= q; i++) printf("%I64d\n", ans[i]);
  return 0;
}
void initialize() {}
int main() {
  int startTime = clock();
  initialize();
  fprintf(stderr, "/--- initializeTime: %ld milliseconds ---/\n",
          clock() - startTime);
  int T = 1;
  startTime = clock();
  while (T--) TaskA();
  fprintf(stderr, "/--- computeTime: %ld milliseconds ---/\n",
          clock() - startTime);
}

```