#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define int ll
int n, q;
int a[200000 + 5];
int x[200000 + 5];
int l[200000 + 5];
int r[200000 + 5];
int mp[800000 + 5];
void discretise() {
vector<int> disc;
for (int i = 0; i < n; ++i) disc.emplace_back(a[i]);
for (int i = 0; i < q; ++i) {
disc.emplace_back(x[i]);
disc.emplace_back(l[i]);
disc.emplace_back(r[i]);
}
sort(disc.begin(), disc.end());
unique(disc.begin(), disc.end());
for (int i = 0; i < n; ++i) {
int orig = a[i];
a[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
mp[a[i]] = orig;
}
for (int i = 0; i < q; ++i) {
int orig = x[i];
x[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
mp[x[i]] = orig;
}
for (int i = 0; i < q; ++i) {
int orig = l[i];
l[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
mp[l[i]] = orig;
}
for (int i = 0; i < q; ++i) {
int orig = r[i];
r[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
mp[r[i]] = orig;
}
}
struct Node {
int l, r, m;
Node *left = nullptr, *right = nullptr;
bool lazy = false;
int val = 0, val2 = 0;
Node(int a, int b) {
l = a, r = b, m = (l + r) / 2;
if (a != b) {
left = new Node(l, m);
right = new Node(m + 1, r);
}
}
void prop() {
if (l == r) return;
if (!lazy) return;
lazy = false;
left->val = 0;
right->val = 0;
left->val2 = 0;
right->val2 = 0;
left->lazy = true;
right->lazy = true;
}
void range_zero(int a, int b) {
if (r < a || b < l) {
return;
}
if (a <= l && r <= b) {
lazy = true;
val = 0;
val2 = 0;
return;
}
prop();
left->range_zero(a, b);
right->range_zero(a, b);
val = left->val + right->val;
val2 = left->val2 + right->val2;
}
void point_update(int p, int v) {
if (l == r) {
val += v;
val2 += v * mp[l];
return;
}
prop();
if (p <= m) left->point_update(p, v);
else right->point_update(p, v);
val = left->val + right->val;
val2 = left->val2 + right->val2;
}
int range_sum(int a, int b) {
if (r < a || b < l) {
return 0;
}
if (a <= l && r <= b) {
return val;
}
prop();
return left->range_sum(a, b) + right->range_sum(a, b);
}
};
Node *root;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < q; ++i) cin >> l[i] >> r[i] >> x[i];
discretise();
root = new Node(0, 800000 + 5);
for (int i = 0; i < n; ++i) {
root->point_update(a[i], 1);
}
cout << root->val2 << '\n';
for (int i = 0; i < q; ++i) {
int num = root->range_sum(l[i], r[i]);
root->range_zero(l[i], r[i]);
root->point_update(x[i], num);
cout << root->val2 << '\n';
}
}
