rt，和这篇题解几乎完全相同，但连样例都过不去，真的找不到哪里有问题，求教。

#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int max_n = 120000, max_s = 131072, max_trs = max_s*4+1, INF = 0x3f3f3f3f;

struct rg
{
	int l, r, id;
	ll ans;
}
qry[max_n];
pair<int, int> smx[max_n], smn[max_n];
int a[max_n], mn[max_trs], tag[max_trs], htm[max_trs];
ll cmn[max_trs], hcmn[max_trs];

inline int ls(int x) { return (x << 1); }
inline int rs(int x) { return (x << 1) | 1; }

void build(int l, int r, int id)
{
	cmn[id] = 1;
	mn[id] = l;
	if (l == r) return;
	
	int mid = (l + r) >> 1;
	build(l, mid, ls(id));
	build(mid + 1, r, rs(id));
}

inline void updmn(int& mn, ll &mnc, int nmn, ll ncmn)
{
	if (mn > nmn)
		mn = nmn, mnc = ncmn;
	else if (mn == nmn)
		mnc += ncmn;
}

inline void updata(int id, int vl)
{
	tag[id] += vl, mn[id] += vl;
}

inline void pushdtg(int id, int vl)
{
	htm[id] += vl;
	hcmn[id] += 1ll * vl * cmn[id];
}

inline void pushup(int id)
{
	mn[id] = INF, cmn[id] = 0;
	updmn(mn[id], cmn[id], mn[ls(id)], cmn[ls(id)]);
	updmn(mn[id], cmn[id], mn[rs(id)], cmn[rs(id)]);
	hcmn[id] = hcmn[ls(id)] + hcmn[rs(id)];
}

inline void pushdown(int id)
{
	updata(ls(id), tag[id]), updata(rs(id), tag[id]);
	tag[id] = 0;
	if (mn[id] == mn[ls(id)]) pushdtg(ls(id), htm[id]);
	if (mn[id] == mn[rs(id)]) pushdtg(rs(id), htm[id]);
	htm[id] = 0;
}

void modify(int L, int R, int l, int r, int id, int vl)
{
	if (L <= l && r <= R)
	{
		updata(id, vl);
		return;
	}
	
	pushdown(id);
	int mid = (l + r) >> 1;
	
	if (L <= mid && l <= R)
		modify(L, R, l, mid, ls(id), vl);
	if (L <= r && mid < R)
		modify(L, R, mid + 1, r, rs(id), vl);
	pushup(id);
}

ll query(int L, int R, int l, int r, int id)
{
	if (L <= l && r <= R)
		return hcmn[id];
	
	pushdown(id);
	int mid = (l + r) >> 1; ll ret = 0;
	
	if (L <= mid && l <= R)
		ret += query(L, R, l, mid, ls(id));
	if (L <= r && mid < R)
		ret += query(L, R, mid + 1, r, rs(id));
	
	cerr << "[" << L << ", " << R << "] in [" << l << ", " <<  r << "] : " << ret << endl;
	return ret;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q;
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	build(1, n, 1);
	
	cin >> q;
	for (int i = 0; i < q; i++)
		cin >> qry[i].l >> qry[i].r, qry[i].id = i, qry[i].l--, qry[i].r--;
	sort(qry, qry + q, [](const rg& lhs, const rg& rhs) { return lhs.r < rhs.r; });
	
	int mxtp = 0, mntp = 0, lst;
	for (int i = 0, qtr = 0; i < n; i++)
	{
		lst = i + 1;
		while (mxtp > 0 && smx[mxtp-1].first < a[i])
			mxtp--, modify(smx[mxtp].second + 1, lst, 1, n, 1, a[i] - smx[mxtp].first), lst = smx[mxtp].second;
		smx[mxtp].first = a[i], smx[mxtp++].second = i;
		lst = i + 1;
		while (mntp > 0 && smn[mntp-1].first > a[i])
			mntp--, modify(smn[mntp].second + 1, lst, 1, n, 1, smn[mntp].first - a[i]), lst = smn[mntp].second;
		smn[mntp].first = a[i], smn[mntp++].second = i;
		updata(1, -1), pushdtg(1, 1);
		
		while (qtr < q && qry[qtr].r <= i)
			qry[qtr].ans = query(qry[qtr].l + 1, i + 1, 1, n, 1), qtr++;
	}
	
	sort(qry, qry + q, [](const rg& lhs, const rg& rhs) { return lhs.id < rhs.id; });
	for (int i = 0; i < q; i++)
		cout << qry[i].ans << endl;
	
	return 0;
}