#include "bits/stdc++.h"
using namespace std;
class Dyanmic_Programming { // O(N^2) DP solution
private:
int N, M;
int A[2005], X[2005], Y[2005], C[2005];
long long DP[2005][2005]; // DP[height][column] = DP with domain(height, column) if we are forced to pick cell (heigth, column).
int Star[2005][2005];
void init() {
for (int i = 0; i < M; i++) {
for (int height = Y[i]; height <= N + 1; height++) {
Star[height][X[i]] = max(Star[height][X[i]], C[i]);
}
}
}
public:
long long solve() {
init();
for (int height = 1; height <= N + 1; height++) { // height N + 1 to merge all components into one
for (int left = 1, right = left; left <= N; left = (++right)) {
if (A[left] >= height) continue; // this cell is still occupied by a building (white cell).
while (right + 1 <= N && A[right + 1] < height) {
right++;
}
// column = left...right is connected to each other, now we find the transition
vector<pair<pair<int, int>, long long>> maximum_values; // maximum values of disjoint domains for cells [height - 1][left...right]
for (int l = left, r = l; l <= right; l = (++r)) {
if (A[l] >= height - 1) continue;
while (r + 1 <= right && A[r + 1] < height - 1) {
r++;
}
{ // with star
long long mx = 0;
for (int k = l; k <= r; k++) {
mx = max(mx, DP[height - 1][k]);
}
maximum_values.push_back({{l, r}, mx});
}
}
long long sum_max_values = 0;
for (auto &values : maximum_values) {
sum_max_values += values.second;
}
for (int column = left; column <= right; column++) {
DP[height][column] = sum_max_values + Star[height][column];
}
for (auto &values : maximum_values) {
for (int column = values.first.first; column <= values.first.second; column++) {
DP[height][column] -= values.second; // This is not necessarily the correct domain and forbidden, so we subtract it
DP[height][column] += DP[height - 1][column] - Star[height - 1][column]; // This is the real domain and forbidden, minus the Star in (height - 1, column).
}
}
}
}
long long sum_all = 0;
long long maximum = 0;
for (int i = 0; i < M; i++) {
sum_all += C[i];
}
for (int i = N + 1; i >= 1; i--) {
for (int j = 1; j <= N; j++) {
if (i == N + 1 ) {
maximum = max(maximum, DP[i][j]);
}
}
}
return sum_all - maximum;
}
void read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
cin >> M;
for (int i = 0; i < M; i++) {
cin >> X[i] >> Y[i] >> C[i];
}
}
};
class Full_Solution {
private:
int N, M;
vector<int> A, X, Y, C;
class DisjointSet {
public:
vector<int> p;
DisjointSet(int n) {
p.resize(n);
iota(begin(p), end(p), 0);
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
};
class SegmentTree {
private:
vector<long long> tree;
vector<long long> lazy;
int sz;
void push(int n) {
for (int c = 0; c < 2; c++) {
tree[n * 2 + c] += lazy[n];
lazy[n * 2 + c] += lazy[n];
}
lazy[n] = 0;
}
void pull(int n) {
tree[n] = max(tree[n * 2], tree[n * 2 + 1]);
}
void RangeSumUpdate(int n, int tl, int tr, int l, int r, long long x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) {
tree[n] += x;
lazy[n] += x;
return;
}
push(n);
int mid = (tl + tr) / 2;
RangeSumUpdate(n * 2, tl, mid, l, r, x);
RangeSumUpdate(n * 2 + 1, mid + 1, tr, l, r, x);
pull(n);
}
long long RangeMaximumQuery(int n, int tl, int tr, int l, int r) {
if (tr < l || r < tl || tl > tr || l > r) return 0;
if (l <= tl && tr <= r) return tree[n];
push(n);
int mid = (tl + tr) / 2;
return max(RangeMaximumQuery(n * 2, tl, mid, l, r),
RangeMaximumQuery(n * 2 + 1, mid + 1, tr, l, r));
}
public:
SegmentTree(int n) {
sz = n;
tree.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
void RangeSumUpdate(int l, int r, long long x) {
return RangeSumUpdate(1, 0, sz - 1, l, r, x);
}
long long RangeMaximumQuery(int l, int r) {
return RangeMaximumQuery(1, 0, sz - 1, l, r);
}
};
vector<vector<pair<int, int>>> CalculateStarDifference() {
vector<vector<pair<int, int>>> StarDifference(N + 2); // SD[height] = Points where Star[height][column] - Star[height - 1][column] > 0, with (column, value)
vector<vector<int>> YCoordinates(N + 1);
vector<vector<int>> stars_per_column(N + 1);
for (int i = 0; i < M; i++) {
YCoordinates[X[i]].emplace_back(Y[i]);
}
for (int i = 1; i <= N; i++) {
sort(begin(YCoordinates[i]), end(YCoordinates[i]));
YCoordinates[i].resize(unique(begin(YCoordinates[i]), end(YCoordinates[i])) - begin(YCoordinates[i]));
}
for (int i = 1; i <= N; i++) {
stars_per_column[i].resize(YCoordinates[i].size());
}
for (int i = 0; i < M; i++) {
int where = lower_bound(begin(YCoordinates[X[i]]), end(YCoordinates[X[i]]), Y[i]) - begin(YCoordinates[X[i]]);
stars_per_column[X[i]][where] = max(stars_per_column[X[i]][where], C[i]);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j < stars_per_column[i].size(); j++) {
stars_per_column[i][j] = max(stars_per_column[i][j], stars_per_column[i][j - 1]);
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < stars_per_column[i].size(); j++) {
int value = stars_per_column[i][j] - (j > 0 ? stars_per_column[i][j - 1] : 0);
StarDifference[YCoordinates[i][j]].emplace_back(i, value);
}
}
return StarDifference;
}
vector<vector<int>> CalculateBuildingsWithHeight() {
vector<vector<int>> BuildingsWithHeight(N + 2); // bwh[height] = A[i] such that A[i] = height - 1
for (int i = 1; i <= N; i++) {
BuildingsWithHeight[A[i] + 1].emplace_back(i);
}
return BuildingsWithHeight;
}
long long SumAll() { // sum of all C[i]
long long res = 0;
for (int i = 0; i < M; i++) {
res += C[i];
}
return res;
}
public:
void read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N;
A.resize(N + 1);
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
cin >> M;
X.resize(M);
Y.resize(M);
C.resize(M);
for (int i = 0; i < M; i++) {
cin >> X[i] >> Y[i] >> C[i];
}
}
long long solve() {
// initialization
vector<vector<pair<int, int>>> StarDifference; // Points where Star[height][column] - Star[height - 1][column] > 0, with (height, value)
StarDifference = CalculateStarDifference();
vector<vector<int>> BuildingsWithHeight(N + 2); // BWH[height] = A[i] such that A[i] = height - 1
BuildingsWithHeight = CalculateBuildingsWithHeight();
// DP optimized with Segment Tree
SegmentTree seg(N + 1);
DisjointSet left_bound(N + 1), right_bound(N + 1); // left and right bound of components
vector<bool> active(N + 1, false); // determine if column is already active (height > A[column])
for (int height = 1; height <= N + 1; height++) {
// Merge Components
vector<pair<int, int>> LR_bounds_old; // to-be-merged components of height - 1
vector<pair<int, int>> LR_bounds_new; // result of merged components of height
for (auto &col : BuildingsWithHeight[height]) {
if (col - 1 >= 1 && active[col - 1]) {
int l = left_bound.Find(col - 1);
int r = right_bound.Find(col - 1);
assert(r == col - 1);
LR_bounds_old.emplace_back(l, r);
}
if (col + 1 <= N && active[col + 1]) {
int l = left_bound.Find(col + 1);
int r = right_bound.Find(col + 1);
assert(l == col + 1);
LR_bounds_old.emplace_back(l, r);
}
}
for (auto &col : BuildingsWithHeight[height]) {
active[col] = true;
if (col - 1 >= 1 && active[col - 1]) {
left_bound.p[col] = col - 1;
right_bound.p[col - 1] = col;
}
if (col + 1 <= N && active[col + 1]) {
right_bound.p[col] = col + 1;
left_bound.p[col + 1] = col;
}
}
for (auto &col : BuildingsWithHeight[height]) {
int l = col, r = col;
if (col - 1 >= 1 && active[col - 1]) l = left_bound.Find(col - 1);
if (col + 1 <= N && active[col + 1]) r = right_bound.Find(col + 1);
LR_bounds_new.emplace_back(l, r);
}
sort(begin(LR_bounds_old), end(LR_bounds_old));
LR_bounds_old.resize(unique(begin(LR_bounds_old), end(LR_bounds_old)) - begin(LR_bounds_old));
sort(begin(LR_bounds_new), end(LR_bounds_new));
LR_bounds_new.resize(unique(begin(LR_bounds_new), end(LR_bounds_new)) - begin(LR_bounds_new));
// Update the DP on Segment Tree
// Add sum_of_maximums_of_previous_components - maximum_this_component
int ptr = 0;
for (auto &new_component : LR_bounds_new) {
long long sum_of_maximums = 0;
for (; ptr < LR_bounds_old.size(); ptr++) {
if (new_component.first <= LR_bounds_old[ptr].first && LR_bounds_old[ptr].second <= new_component.second) {
long long current_maximum = seg.RangeMaximumQuery(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second);
seg.RangeSumUpdate(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second, -current_maximum);
sum_of_maximums += current_maximum;
} else if (new_component.second < LR_bounds_old[ptr].first) {
break;
}
}
seg.RangeSumUpdate(new_component.first, new_component.second, sum_of_maximums);
}
// Add StarDifference (Star[height][column] - Star[height - 1][column])
for (auto &stars : StarDifference[height]) {
int column = stars.first;
int value = stars.second;
seg.RangeSumUpdate(column, column, value);
}
}
return SumAll() - seg.RangeMaximumQuery(1, N);
}
};
int main() {
Full_Solution Solver;
Solver.read();
cout << Solver.solve() << "\n";
return 0;
}
