跑 $n = 500000$ 5.17s.... 求优化，优化好久了

题在这里，过了就说明没问题了(无题面

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #include <iostream>
#include <stdio.h>
// #include <cstring>
#include <string.h>
// #include <cmath>
#include <math.h>
#define N 1000005
#define INF 0x3f3f3f3f
const int DPAIRSIZ = 1 << 18;
char *p1, *p2, buf[100000];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
int read()
{
    int x = 0;
    int fu = 1;
    char c = getchar();
    while (c > 57 || c < 48)
    {
        if (c == 45)
            fu = -1;
        c = getchar();
    }
    while (c <= 57 && c >= 48)
    {
        x = x * 10 + c - 48;
        c = getchar();
    }
    return x * fu;
}
int maxx(int x, int y)
{
    return x > y ? x : y;
}
int minnn(int x, int y)
{
    return x < y ? x : y;
}
int n, a[N], L, R;
int maxn[(N << 2) + 1];
int minn[(N << 2) + 1];
#define push_up(k) maxn[k] = maxx(maxn[k << 1], maxn[k << 1 | 1])
#define push_up1(k) minn[k] = minnn(minn[k << 1], minn[k << 1 | 1])
void build(int l, int r, int k)
{
    if (l == r)
    {
        maxn[k] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, k << 1);
    build(mid + 1, r, k << 1 | 1);
    push_up(k);
}
int ql, qr;
int query(int l, int r, int k)
{
    int ret = -INF;
    if (l >= ql && r <= qr)
        return maxn[k];
    int mid = (l + r) >> 1;
    if (ql <= mid)
        ret = maxx(ret, query(l, mid, k << 1));
    if (qr > mid)
        ret = maxx(ret, query(mid + 1, r, k << 1 | 1));
    return ret;
}
void build1(int l, int r, int k)
{
    if (l == r)
    {
        minn[k] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build1(l, mid, k << 1);
    build1(mid + 1, r, k << 1 | 1);
    push_up1(k);
}
int query1(int l, int r, int k)
{
    int ret = INF;
    if (l >= ql && r <= qr)
        return minn[k];
    int mid = (l + r) >> 1;
    if (ql <= mid)
        ret = minnn(ret, query1(l, mid, k << 1));
    if (qr > mid)
        ret = minnn(ret, query1(mid + 1, r, k << 1 | 1));
    return ret;
}

int check(int tl, int tr)
{
    ql = tl, qr = tr;
    int judge1 = query(1, n, 1), judge = query1(1, n, 1);
    if (L <= judge1 - judge && judge1 - judge <= R)
    {
        return 1;
    }
    else
        return 0;
}

int Ans = 0, l, r, ans1, ans2, i, judge, judge1;
int main()
{
    // cin >> n >> L >> R;
    n = read();
    L = read();
    R = read();
    memset(a, 0, sizeof a);
    for (int i = 1; i <= n; i = -~i)
        read(a[i]);
    memset(maxn, 0, sizeof maxn);
    memset(minn, 0, sizeof minn);
    build(1, n, 1), build1(1, n, 1);
    for (i = 1; i <= n; i = -~i)
    {
        l = i, r = n, ans1 = i, ans2 = i;
        while (l <= r)
        {
            int mid = l + r >> 1;
            int tl = i, tr = mid;
            ql = tl, qr = tr;
            judge1 = query(1, n, 1), judge = query1(1, n, 1);
            if (L <= judge1 - judge && judge1 - judge <= R)
                ans1 = mid, l = mid + 1;
            else
            {
                if (judge1 - judge > R)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }
        l = i, r = n;
        while (l <= r)
        {
            int mid = l + r >> 1;
            int tl = i, tr = mid;
            ql = tl, qr = tr;
            judge1 = query(1, n, 1), judge = query1(1, n, 1);
            if (L <= judge1 - judge && judge1 - judge <= R)
                ans2 = mid, r = mid - 1;
            else
            {
                if (judge1 - judge > R)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }
        if (check(i, ans1) || check(i, ans2))
            Ans += (ans1 - ans2) + 1;
    }
    // cout << Ans;
    printf("%d", Ans);
    return 0;
}