#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector")
#pragma GCC target("tune=native")
using namespace std;
using ll = long long;
const size_t ML = 64E6;
char allocated[ML], *first_free = allocated;
void *operator new(size_t n) {
  char *res = first_free;
  first_free += n;
  return (void *)res;
}
void operator delete(void *) noexcept {}
void operator delete(void *, size_t) noexcept {}
const size_t BUFSIZE = 1 << 19;
char read_buf[BUFSIZE], write_buf[BUFSIZE];
size_t read_len = 0, read_pos = 0, write_pos = 0;
inline bool can_read() {
  if (read_pos == read_len) {
    read_pos = 0;
    read_len = fread(read_buf, 1, BUFSIZE, stdin);
  }
  return read_pos != read_len;
}
void flush() {
  fwrite(write_buf, 1, write_pos, stdout);
  write_pos = 0;
}
inline char get_char() { return can_read() ? read_buf[read_pos++] : -1; }
inline void write_char(char x) {
  if (write_pos == BUFSIZE) flush();
  write_buf[write_pos++] = x;
}
inline char read_char() {
  char c = get_char();
  while (0 <= c && c <= 32) c = get_char();
  return c;
}
template <class T>
inline void read_int(T &sum) {
  int sign = +1, c = read_char();
  sum = 0;
  if (c == '-') sign = -1, c = get_char();
  while ('0' <= c && c <= '9') {
    sum = 10 * sum + (c ^ 48);
    c = get_char();
  }
  sum *= sign;
}
template <class T>
inline void write_int(T x) {
  static char s[31];
  size_t n = 0;
  if (x < 0) write_char('-'), x = -x;
  for (; !n || x; x /= 10) s[n++] = (char)((x % 10) ^ 48);
  while (n--) write_char(s[n]);
}
void read_word(char *word) {
  char c = read_char();
  while (c >= 32) {
    *(word++) = c;
    c = get_char();
  }
}
void write_word(char *word) {
  for (; *word; ++word) {
    write_char(*word);
  }
}
const int N = 120005;
struct node_t {
  int tag, time, value, number;
  ll answer;
} tree[N << 2];
int n, m, top_max, top_min, a[N], stack_max[N], stack_min[N];
vector<pair<int, int>> queries[N];
ll answer[N];
void add_value(int x, int value) {
  tree[x].value += value;
  tree[x].tag += value;
}
void add_time(int x, int value) {
  tree[x].time += value;
  tree[x].answer += (ll)value * tree[x].number;
}
void push_up(int x) {
  tree[x].value = min(tree[x << 1].value, tree[x << 1 | 1].value);
  tree[x].answer = tree[x << 1].answer + tree[x << 1 | 1].answer;
  tree[x].number = 0;
  if (tree[x].value == tree[x << 1].value) {
    tree[x].number += tree[x << 1].number;
  }
  if (tree[x].value == tree[x << 1 | 1].value) {
    tree[x].number += tree[x << 1 | 1].number;
  }
}
void push_down(int x) {
  if (tree[x].tag) {
    add_value(x << 1, tree[x].tag);
    add_value(x << 1 | 1, tree[x].tag);
    tree[x].tag = 0;
  }
  if (tree[x].time) {
    if (tree[x].value == tree[x << 1].value) {
      add_time(x << 1, tree[x].time);
    }
    if (tree[x].value == tree[x << 1 | 1].value) {
      add_time(x << 1 | 1, tree[x].time);
    }
    tree[x].time = 0;
  }
}
void build(int x, int l, int r) {
  tree[x].value = l;
  tree[x].number = 1;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
void modify(int x, int l, int r, int ql, int qr, int value) {
  if (l == ql && r == qr) {
    add_value(x, value);
    return;
  }
  int mid = (l + r) / 2;
  push_down(x);
  if (qr <= mid) {
    modify(x << 1, l, mid, ql, qr, value);
  } else if (ql > mid) {
    modify(x << 1 | 1, mid + 1, r, ql, qr, value);
  } else {
    modify(x << 1, l, mid, ql, mid, value);
    modify(x << 1 | 1, mid + 1, r, mid + 1, qr, value);
  }
  push_up(x);
}
ll query(int x, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return tree[x].answer;
  }
  int mid = (l + r) / 2;
  push_down(x);
  if (qr <= mid) {
    return query(x << 1, l, mid, ql, qr);
  } else if (ql > mid) {
    return query(x << 1 | 1, mid + 1, r, ql, qr);
  } else {
    return query(x << 1, l, mid, ql, mid) +
           query(x << 1 | 1, mid + 1, r, mid + 1, qr);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  read_int(n);
  for (int i = 1; i <= n; ++i) {
    read_int(a[i]);
  }
  read_int(m);
  for (int i = 1; i <= m; ++i) {
    int l, r;
    read_int(l);
    read_int(r);
    queries[r].push_back(make_pair(l, i));
  }
  build(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    add_value(1, -1);
    while (top_max && a[stack_max[top_max]] < a[i]) {
      modify(1, 1, n, stack_max[top_max - 1] + 1, stack_max[top_max],
             a[i] - a[stack_max[top_max]]);
      --top_max;
    }
    stack_max[++top_max] = i;
    while (top_min && a[stack_min[top_min]] > a[i]) {
      modify(1, 1, n, stack_min[top_min - 1] + 1, stack_min[top_min],
             a[stack_min[top_min]] - a[i]);
      --top_min;
    }
    stack_min[++top_min] = i;
    add_time(1, 1);
    for (auto q : queries[i]) {
      answer[q.second] = query(1, 1, n, q.first, i);
    }
  }
  for (int i = 1; i <= m; ++i) {
    write_int(answer[i]);
    write_char('\n');
  }
  flush();
  return 0;
}
