我写了一个显然可以卡到 $\Theta(n^2)$ 的代码，结果A了？？？？？？？

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

#define Int register int
#define mod 1000000000
#define MAXN 500005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,val[MAXN],pre[MAXN],suf[MAXN],getf[MAXN],fucf[MAXN];
int sqr (int x){return 1ll * x * x % mod;}
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

int cdq (int l,int r){
	if (l > r) return 0;
	if (l == r) return sqr (val[l]);
	int mid = 0,res;for (Int i = l;i <= r;++ i) if (!mid || val[i] <= val[mid]) mid = i;
	res = add (cdq (l,mid - 1),cdq (mid + 1,r)),pre[0] = suf[0] = fucf[0] = val[mid];
	for (Int i = mid - 1;i >= l;-- i) suf[mid - i] = max (suf[mid - i - 1],val[i]);
	for (Int i = mid + 1;i <= r;++ i) pre[i - mid] = max (pre[i - mid - 1],val[i]),getf[i - mid] = add (getf[i - mid - 1],mul (pre[i - mid],i - mid)),fucf[i - mid] = add (fucf[i - mid - 1],pre[i - mid]);
	int len1 = mid - l,len2 = r - mid,tot = 0;
	for (Int i = 0;i <= len1;++ i){
		while (tot < len2 && pre[tot + 1] <= suf[i]) ++ tot;
		res = add (res,mul (val[mid],mul (suf[i],1ll * (2 * i + tot + 2) * (tot + 1) / 2 % mod)));
		res = add (res,mul (val[mid],mul (i + 1,dec (fucf[len2],fucf[tot])))),res = add (res,mul (val[mid],dec (getf[len2],getf[tot])));
	}
	return res;
}

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (val[i]);
	write (cdq (1,n)),putchar ('\n');
 	return 0;
}

@小粉兔