题

给定长度为 $n$ 的序列 $a$。
定义 $Max(l,r)$ 为 $a_l\dots a_r$ 的最大值，$Min(l,r)$ 同理。求：
$\sum_{l=1}^n\sum_{r=l}^n Max(l,r)\times Min(l,r)$ 对 $998244353$ 取模。
$1\le n\le 10^5$，$1\le a_i\le 10^9$。

分治，对于区间 $L$ 到 $R$，考虑 $l=L \dots mid$，$r=mid+1 \dots R$ 的区间造成的贡献。

我们记录三个指针：

• $i$，表示现在考虑到了 $l=i$，$r=mid+1 \dots R$ 这部分区间。 $i$ 从 $mid$ 开始向前枚举，可以在这个过程中记录 $[i,mid]$ 的最值 $lmx$ 和 $lmn$，显然这两个东西是单调的；

• $j$，表示对于当前 $i$，在 $r=mid+1 \dots j$ 时左半部分最大值占主导地位，即 $Max(mid+1,r)<=Max(i,mid),r=mid+1 \dots j$。显然这个东西也是单调的。

• $k$，与 $j$ 类似，不过是最小值。

然后可以把 $l=i,r=mid+1 \dots R$ 这部分区间分成三部分：

• $mid+1 \dots\min(j, k)$ 所有最值都是左边占主导，每个区间贡献都是 $lmx\times lmn$；
• $\max(j, k) + 1 \dots R$ 所有最值都是右边主导，可预处理 $Max(mid+1,r)\times Min(mid+1,r)$ 的前缀和快速得到；
• $\min(j,k) + 1 \dots \max(j,k) $$，一部分左边主导，预处理右边 $Max$ 和 $Min$ 的前缀和即可。

然后就做完了 qwq。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 100005
#define P 1000000007

int n, a[N], res, mn[N], mx[N], smn[N], smx[N], s[N];

void cdx(int l, int r) {
	if (l == r) {
		res = (res + a[l] * a[r] % P) % P;
		return;
	}
	int mid = (l + r) >> 1;
	cdx(l, mid), cdx(mid + 1, r);
	mn[mid] = 1e9, mx[mid] = 0;
	s[mid] = smx[mid] = smn[mid] = 0;
	for (int i = mid + 1; i <= r; i ++) {
		mn[i] = min(mn[i - 1], a[i]);
		mx[i] = max(mx[i - 1], a[i]);
		s[i] = (s[i - 1] + mn[i] * mx[i] % P) % P;
	}
	mn[mid] = 0;
	for (int i = mid + 1; i <= r; i ++) {
		smn[i] = (smn[i - 1] + mn[i]) % P;
		smx[i] = (smx[i - 1] + mx[i]) % P;
	}	
	for (int i = mid, j = mid, k = mid, lmx = 0, lmn = 1e9; i >= l; i --) {
		lmx = max(lmx, a[i]), lmn = min(lmn, a[i]);
		while (j < r && mx[j + 1] <= lmx) j ++;
		while (k < r && mn[k + 1] >= lmn) k ++;
		(res += (s[r] - s[max(j, k)] + P) % P) %= P;
		(res += lmx * lmn % P * max(0ll, min(j, k) - mid) % P) %= P;
		if (j <= k) (res += lmn * ((smx[k] - smx[j] + P) % P) % P) %= P;
		else 		(res += lmx * ((smn[j] - smn[k] + P) % P) % P) %= P;
	}
	for (int i = mid; i <= r; i ++) mn[i] = mx[i] = s[i] = 0;
}

signed main() {
	freopen("simple.in", "r", stdin);
	freopen("simple.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; i ++) {
		a[i] = read();
	}
	cdx(1, n), printf("%lld\n", res);
	return 0;
}