#include <bits/stdc++.h>
template <typename T>
class segment_tree {
private:
std::size_t _n, n;
std::vector<T> seg;
public:
segment_tree(std::size_t _n) : _n(_n), n(std::bit_ceil(_n)), seg(2 * n) {}
void set(std::size_t i, const T &x) {
for (seg[i += n] = x, i /= 2; i > 0; i /= 2) {
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
}
T query(std::size_t l, std::size_t r) const {
T ans_l = T{}, ans_r = T{};
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1)
ans_l = ans_l + seg[l++];
if (r & 1)
ans_r = seg[--r] + ans_r;
}
return ans_l + ans_r;
}
const T &at(std::size_t i) const { return seg[n + i]; }
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
struct node {
int x, i;
node(int x, int i) : x(x), i(i) {}
node() : x(-1), i(-1) {}
node operator+(const node &other) const {
if (x != other.x) {
return x > other.x ? *this : other;
}
return i < other.i ? *this : other;
}
};
segment_tree<node> st(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
st.set(i, {a[i], i});
}
auto iterate = [&](int ql, int qr, int qx) {
std::vector<int> ans;
int l = ql;
while (l <= qr) {
auto [x, i] = st.query(l, qr);
if (x != qx) {
break;
}
ans.push_back(i);
l = i + 1;
}
return ans;
};
struct node_info {
int l, r; // left and right intervals of the node
int s, e; // for example, starts from height n+1 and ends at height n-2 (as arrays)
};
std::vector<node_info> info(n);
std::vector<std::vector<int>> adj(n + 1); // stores the cartesian tree
struct point {
int x, y, c;
};
std::vector<std::vector<point>> points(n + 1); // points associated with a node in the cartesian tree
info[0] = {.l = 0, .r = n - 1, .s = n + 1};
// when we enter a node, we know l,r,s, and don't know e, which we need to find out
int label = 0; // marker for the node we're currently at
auto build = [&](auto &&self, int u) {
auto [qx, qi] = st.query(info[u].l, info[u].r);
info[u].e = qx + 1;
if (info[u].l == info[u].r) { // base case when we're at the leaf
return;
}
int x = qx, i = qi;
int l = info[u].l;
auto vals = iterate(info[u].l, info[u].r, x);
vals.push_back(info[u].r + 1);
for (int &pos : vals) {
if (l > pos - 1) {
l = pos + 1;
continue;
}
int to = label++;
adj[u].push_back(to);
info[to].l = l, info[to].r = pos - 1;
info[to].s = x;
self(self, to);
l = pos + 1;
}
};
build(build, label++);
// search up, for each point, which cartesian tree node it is part of
struct rect {
int x1, y1, x2, y2, i;
};
std::vector<rect> rects(label);
for (int i = 0; i < label; ++i) {
rects[i] = {.x1 = info[i].l, .y1 = info[i].e, .x2 = info[i].r, .y2 = info[i].s, .i = i};
}
// need to build an offline sweep data structure
int m;
std::cin >> m;
int64_t tot = 0;
struct raw_point {
int x, y;
bool operator<(const raw_point &other) const {
if (x != other.x) {
return x < other.x;
}
return y < other.y;
}
};
std::vector<point> inp_points;
std::vector<raw_point> buf; // buf is the set of queries
for (int i = 0, x, y, c; i < m; ++i) {
std::cin >> x >> y >> c;
--x;
buf.push_back({x, y});
inp_points.push_back({x, y, c});
tot += c;
buf.push_back({x, a[x] + 1}); // we'd wanna queries demotes as well
}
struct rect_in {
std::vector<rect> rects;
std::vector<raw_point> buf;
std::vector<int> ans;
int n;
rect_in(std::vector<rect> _rects, std::vector<raw_point> _buf) : n(_buf.size()), rects(_rects), buf(_buf), ans(_buf.size(), -1) {
std::sort(buf.begin(), buf.end());
struct event {
int type; // 0: add, 1: query, 2: remove
int x, i;
bool operator<(const event &other) const {
if (x != other.x) {
return x < other.x;
}
return type < other.type;
}
};
std::vector<event> events;
for (int i = 0; i < rects.size(); ++i) {
events.push_back({.type = 0, .x = rects[i].x1, .i = i});
events.push_back({.type = 2, .x = rects[i].x2 + 1, .i = i});
}
for (int i = 0; i < n; ++i) {
events.push_back({.type = 1, .x = buf[i].x, .i = i});
}
std::sort(events.begin(), events.end());
std::set<std::pair<int, int>> ys; // active y vals
for (auto &[type, x, i] : events) {
if (type == 0) {
ys.insert({rects[i].y1, i});
} else if (type == 1) {
std::pair<int, int> p = {buf[i].y, std::numeric_limits<int>::max()};
auto it = ys.upper_bound(p);
assert(it != ys.begin());
--it;
assert(buf[i].y >= rects[it->second].y1 and buf[i].y <= rects[it->second].y2);
ans[i] = it->second;
} else {
ys.erase({rects[i].y1, i});
}
}
}
int query(int x, int y) {
raw_point p{x, y};
auto it = std::lower_bound(buf.begin(), buf.end(), p);
assert(it != buf.end());
assert(ans[it - buf.begin()] != -1);
return ans[it - buf.begin()];
}
};
rect_in sweep(rects, buf);
// add the points belonging to each rectangle
for (int i = 0; i < m; ++i) {
auto [x, y, c] = inp_points[i];
points[sweep.query(x, y)].push_back({x, y, c});
}
// perform an euler tour on the cartesian tree to get sums from the root to each node
std::vector<int> in(label), out(label);
int timer = 0;
auto dfs_euler = [&](auto &&self, int u) -> void {
in[u] = timer++;
for (int &i : adj[u]) {
self(self, i);
}
out[u] = timer - 1;
};
dfs_euler(dfs_euler, 0); // now the subtree of u is [start[u], end[u]]
segment_tree<int64_t> path_st(label + 1); // a difference array segtree
auto add = [&](int u, int64_t x) {
path_st.set(in[u], path_st.at(in[u]) + x);
path_st.set(out[u] + 1, path_st.at(out[u] + 1) - x);
};
auto query_from_root = [&](int u) {
return path_st.query(0, in[u]);
};
auto query = [&](int low, int high) { // needs high to be a parent of low
return query_from_root(low) - query_from_root(high);
};
// perform tree dp on the cartesian tree
std::vector<int64_t> dp(label), contrib(label); // contrib[u] is just what we ended up picking from u
auto dfs = [&](auto &&self, int u) -> void {
for (int &i : adj[u]) {
self(self, i);
}
// either we exclude all points
for (int &i : adj[u]) {
dp[u] += dp[i];
}
int64_t tot = dp[u];
// or we choose exactly 1 point
for (auto &[x, y, c] : points[u]) {
int64_t cur = tot - query(sweep.query(x, a[x] + 1), u) + c;
if (cur > dp[u]) {
dp[u] = cur;
add(u, c - contrib[u]);
contrib[u] = c;
}
}
};
dfs(dfs, 0);
std::cout << tot - dp[0] << '\n';
}
