AC代码（单调队列优化）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, a[maxn], p[maxn];
long long f[maxn];
struct Line {
	int l, r;
} b[maxn];

bool cmp(Line a, Line b) {
	return a.r < b.r;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++)
		cin >> b[i].l >> b[i].r;
	sort(b+1, b+m+1, cmp);
	for (int i = 1, j = 1, tmp = 0; i <= n + 1; i++) {
		while (j <= m && b[j].r < i)
			tmp = max(tmp, b[j].l), j++;
		p[i] = tmp;
	}
	deque<int> que;
	for (int i = 1; i <= n + 1; i++) {
		f[i] = 1e18;
		while (!que.empty() && f[que.back()] >= f[i-1])
			que.pop_back();
		que.push_back(i-1);
		while (!que.empty() && que.front() < p[i])
			que.pop_front();
		// [ p[i], i-1 ]
		f[i] = f[que.front()] + a[i];
	}
	cout << f[n+1] << endl;
	return 0;
}

$O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, a[maxn], p[maxn];
long long f[maxn];
struct Line {
	int l, r;
} b[maxn];

bool cmp(Line a, Line b) {
	return a.r < b.r;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++)
		cin >> b[i].l >> b[i].r;
	sort(b+1, b+m+1, cmp);
	for (int i = 1, j = 1, tmp = 0; i <= n + 1; i++) {
		while (j <= m && b[j].r < i)
			tmp = max(tmp, b[j].l), j++;
		p[i] = tmp;
	}
	for (int i = 1; i <= n + 1; i++) {
		f[i] = 1e18;
		for (int j = p[i]; j < i; j++)
			f[i] = min(f[i], f[j] + a[i]);
//		cout << i << " : " << f[i] << endl;
	}
	cout << f[n+1] << endl; // O(n^2)
	return 0;
}