func_code_string: #include <bits/stdc++.h>   using namespace std;   inline long long read() {     register long long data = 0, w = 1;     char ch = 0;     while (ch !=  -  && (ch <  0  || ch >  9 )) ch = getchar();     if (ch ==  - ) w = -1, ch = getchar();     while (ch >=  0  && ch <=  9 )       data = (data << 1) + (data << 3) + (ch ^ 48), ch = getchar();     return data * w;   }   long long st1[1000005], st2[1000005], top1, top2, js[1000005], mi[1000005],       ans[1000005], ti[1000005], ad[1000005];   void pushup(long long x) {     long long l = x << 1, r = x << 1 | 1;     ans[x] = ans[l] + ans[r];     mi[x] = min(mi[l], mi[r]);     js[x] = 0;     if (mi[l] == mi[x]) js[x] += js[l];     if (mi[r] == mi[x]) js[x] += js[r];   }   void add(long long x, long long v) {     mi[x] += v;     ad[x] += v;   }   void addti(long long x, long long v) {     ans[x] += v * js[x];     ti[x] += v;   }   void pushdown(long long x) {     if (ad[x]) add(x << 1, ad[x]), add(x << 1 | 1, ad[x]);     if (ti[x]) {       if (mi[x << 1] == mi[x]) addti(x << 1, ti[x]);       if (mi[x << 1 | 1] == mi[x]) addti(x << 1 | 1, ti[x]);     }     ad[x] = ti[x] = 0;   }   void build(long long x, long long l, long long r) {     js[x] = 1;     mi[x] = l;     if (l == r) return;     long long mid = l + r >> 1;     build(x << 1, l, mid);     build(x << 1 | 1, mid + 1, r);   }   void add(long long x, long long l, long long r, long long ql, long long qr,            long long v) {     if (ql <= l && r <= qr) return add(x, v);     long long mid = l + r >> 1;     pushdown(x);     if (ql <= mid) add(x << 1, l, mid, ql, qr, v);     if (mid < qr) add(x << 1 | 1, mid + 1, r, ql, qr, v);     pushup(x);   }   long long ask(long long x, long long l, long long r, long long ql,                 long long qr) {     if (ql > r || qr < l) return 0;     if (ql <= l && r <= qr) return ans[x];     pushdown(x);     long long mid = l + r >> 1;     return ask(x << 1, l, mid, ql, qr) + ask(x << 1 | 1, mid + 1, r, ql, qr);   }   long long a[1000005], Ans[1000005];   struct que {     long long l, r, id;   } q[1000005];   int main() {     long long n = read();     for (long long i = 1; i <= n; i++) a[i] = read();     build(1, 1, n);     long long Q = read();     for (long long i = 1; i <= Q; i++)       q[i].l = read(), q[i].r = read(), q[i].id = i;     sort(q + 1, q + Q + 1, [](que A, que B) { return A.r < B.r; });     long long j = 1;     for (long long i = 1; i <= n; i++) {       add(1, -1);       while (top1 && a[i] > a[st1[top1]])         add(1, 1, n, st1[top1 - 1] + 1, st1[top1], a[i] - a[st1[top1]]), --top1;       st1[++top1] = i;       while (top2 && a[i] < a[st2[top2]])         add(1, 1, n, st2[top2 - 1] + 1, st2[top2], a[st2[top2]] - a[i]), --top2;       st2[++top2] = i;       addti(1, 1);       while (j <= Q && q[j].r == i)         Ans[q[j].id] = ask(1, 1, n, q[j].l, q[j].r), ++j;     }     for (long long i = 1; i <= Q; i++) cout << Ans[i] <<   n ;     return 0;   }   