#include <bits/stdc++.h>
#define base 1000000007LL
#define ll long long
#define ld long double
#define X first
#define Y second
#define pb push_back
#define EPS 1e-6
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
using namespace std;
typedef pair<int, int> II;
typedef pair<II, int> III;
set<II> lefval, rigval;
int n, m, h[100010];
ll sum[100010], res;
void update(int u, int gt)
{
while (u <= n) {
sum[u] += gt;
u = u + (u & (-u));
}
}
ll getSum(int u)
{
ll res = 0;
while (u) {
res += sum[u];
u = u - (u & (-u));
}
return res;
}
ll calc(int l, int r, ll pre)
{
if (l == 0 || r == n+1) return 0;
ll t = getSum(r) - getSum(l-1);
ll res = pre * (r-l+1) - t;
return res;
}
void upA(int u, int v)
{
set<II>::iterator it = lefval.lower_bound(II(u, h[u]));
if (it == lefval.end()) {
it--;
if (h[u]+v > it->Y) {
res += calc(it->X, u-1, it->Y);
lefval.insert(II(u, h[u]+v));
}
return;
}
int MaxL, vtL;
if (lefval.count(II(u, h[u]))) {
MaxL = h[u];
vtL = u;
lefval.erase(II(u, h[u]));
}
else {
it--;
if (h[u] + v <= it->Y) {
res -= v;
return;
}
vtL = u;
MaxL = it->Y;
}
while (1) {
it = lefval.lower_bound(II(u, 0));
if (it == lefval.end()) break;
res -= calc(vtL, it->X-1, MaxL);
if (h[u]+v < it->Y) {
res += calc(u, it->X-1, h[u]+v);
res -= v;
break;
}
vtL = it->X;
MaxL = it->Y;
lefval.erase(it);
}
lefval.insert(II(u, h[u]+v));
}
void upB(int u, int v)
{
set<II>::iterator it = rigval.lower_bound(II(-u, h[u]));
if (it == rigval.end()) {
it--;
if (h[u]+v >= it->Y) {
res += calc(u+1, -it->X, it->Y);
rigval.insert(II(-u, h[u]+v));
}
return;
}
int MaxR, vtR;
if (rigval.count(II(-u, h[u]))) {
MaxR = h[u];
vtR = u;
rigval.erase(II(-u, h[u]));
}
else {
it--;
if (h[u] + v < it->Y) {
res -= v;
return;
}
vtR = u;
MaxR = it->Y;
}
while (1) {
it = rigval.lower_bound(II(-u, 0));
if (it == rigval.end()) break;
res -= calc(-it->X+1, vtR, MaxR);
if (h[u]+v <= it->Y) {
res += calc(-it->X+1, u, h[u]+v);
res -= v;
break;
}
vtR = -it->X;
MaxR = it->Y;
rigval.erase(it);
}
rigval.insert(II(-u, h[u]+v));
}
int main()
{
ios::sync_with_stdio(0);
//freopen("inp.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int te;
scanf("%d", &te);
while (te--) {
scanf("%d", &n);
scanf("%d", &m);
ms(sum, 0);
FOR(i,1,n) {
scanf("%d", &h[i]);
update(i, h[i]);
}
scanf("\n");
int MaxL = 0, vtL = 0;
res = 0;
lefval.clear();
rigval.clear();
FOR(i,1,n)
if (h[i] > MaxL) {
res += calc(vtL, i-1, MaxL);
MaxL = h[i];
vtL = i;
lefval.insert(II(i,h[i]));
}
int MaxR = 0, vtR = n+1;
FORE(i,n,1)
if (h[i] >= MaxR) {
res += calc(i+1, vtR, MaxR);
MaxR = h[i];
vtR = i;
rigval.insert(II(-i,h[i]));
}
while (m--) {
char ch; int u, v;
scanf("%c", &ch);
if (ch == 'P') {
scanf("\n");
printf("%I64d\n", res);
}
else {
scanf("%d", &u);
scanf("%d\n", &v);
upA(u, v);
upB(u, v);
/*printf("\n");
FORALL(it, rigval) printf("%d %d\n", it->X, it->Y);
printf("\n");*/
h[u] += v;
update(u, v);
}
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgYmFzZSAxMDAwMDAwMDA3TEwKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBsZCBsb25nIGRvdWJsZQojZGVmaW5lIFggZmlyc3QKI2RlZmluZSBZIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIEVQUyAxZS02CiNkZWZpbmUgYWxsKGEpIChhKS5iZWdpbigpLCAoYSkuZW5kKCkKI2RlZmluZSBzeihhKSBpbnQoKGEpLnNpemUoKSkKI2RlZmluZSBtcyhzLCBuKSBtZW1zZXQocywgbiwgc2l6ZW9mKHMpKQojZGVmaW5lIEZPUihpLGEsYikgZm9yIChpbnQgaSA9IChhKTsgaSA8PSAoYik7IGkrKykKI2RlZmluZSBGT1JFKGksYSxiKSBmb3IgKGludCBpID0gKGEpOyBpID49IChiKTsgaS0tKQojZGVmaW5lIEZPUkFMTChpdCwgYSkgZm9yIChfX3R5cGVvZigoYSkuYmVnaW4oKSkgaXQgPSAoYSkuYmVnaW4oKTsgaXQgIT0gKGEpLmVuZCgpOyBpdCsrKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IElJOwp0eXBlZGVmIHBhaXI8SUksIGludD4gSUlJOwoKc2V0PElJPiBsZWZ2YWwsIHJpZ3ZhbDsKaW50IG4sIG0sIGhbMTAwMDEwXTsKbGwgc3VtWzEwMDAxMF0sIHJlczsKCnZvaWQgdXBkYXRlKGludCB1LCBpbnQgZ3QpCnsKICAgIHdoaWxlICh1IDw9IG4pIHsKICAgICAgICBzdW1bdV0gKz0gZ3Q7CiAgICAgICAgdSA9IHUgKyAodSAmICgtdSkpOwogICAgfQp9CgpsbCBnZXRTdW0oaW50IHUpCnsKICAgIGxsIHJlcyA9IDA7CiAgICB3aGlsZSAodSkgewogICAgICAgIHJlcyArPSBzdW1bdV07CiAgICAgICAgdSA9IHUgLSAodSAmICgtdSkpOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoKbGwgY2FsYyhpbnQgbCwgaW50IHIsIGxsIHByZSkKewogICAgaWYgKGwgPT0gMCB8fCByID09IG4rMSkgcmV0dXJuIDA7CiAgICBsbCB0ID0gZ2V0U3VtKHIpIC0gZ2V0U3VtKGwtMSk7CiAgICBsbCByZXMgPSBwcmUgKiAoci1sKzEpIC0gdDsKICAgIHJldHVybiByZXM7Cn0KCnZvaWQgdXBBKGludCB1LCBpbnQgdikKewogICAgc2V0PElJPjo6aXRlcmF0b3IgaXQgPSBsZWZ2YWwubG93ZXJfYm91bmQoSUkodSwgaFt1XSkpOwogICAgaWYgKGl0ID09IGxlZnZhbC5lbmQoKSkgewogICAgICAgIGl0LS07CiAgICAgICAgaWYgKGhbdV0rdiA+IGl0LT5ZKSB7CiAgICAgICAgICAgIHJlcyArPSBjYWxjKGl0LT5YLCB1LTEsIGl0LT5ZKTsKICAgICAgICAgICAgbGVmdmFsLmluc2VydChJSSh1LCBoW3VdK3YpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IE1heEwsIHZ0TDsKICAgIGlmIChsZWZ2YWwuY291bnQoSUkodSwgaFt1XSkpKSB7CiAgICAgICAgTWF4TCA9IGhbdV07CiAgICAgICAgdnRMID0gdTsKICAgICAgICBsZWZ2YWwuZXJhc2UoSUkodSwgaFt1XSkpOwogICAgfQogICAgZWxzZSB7CiAgICAgICAgaXQtLTsKICAgICAgICBpZiAoaFt1XSArIHYgPD0gaXQtPlkpIHsKICAgICAgICAgICAgcmVzIC09IHY7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgdnRMID0gdTsKICAgICAgICBNYXhMID0gaXQtPlk7CiAgICB9CiAgICB3aGlsZSAoMSkgewogICAgICAgIGl0ID0gbGVmdmFsLmxvd2VyX2JvdW5kKElJKHUsIDApKTsKICAgICAgICBpZiAoaXQgPT0gbGVmdmFsLmVuZCgpKSBicmVhazsKICAgICAgICByZXMgLT0gY2FsYyh2dEwsIGl0LT5YLTEsIE1heEwpOwoKICAgICAgICBpZiAoaFt1XSt2IDwgaXQtPlkpIHsKICAgICAgICAgICAgcmVzICs9IGNhbGModSwgaXQtPlgtMSwgaFt1XSt2KTsKICAgICAgICAgICAgcmVzIC09IHY7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICB2dEwgPSBpdC0+WDsKICAgICAgICBNYXhMID0gaXQtPlk7CiAgICAgICAgbGVmdmFsLmVyYXNlKGl0KTsKICAgIH0KICAgIGxlZnZhbC5pbnNlcnQoSUkodSwgaFt1XSt2KSk7Cn0KCnZvaWQgdXBCKGludCB1LCBpbnQgdikKewogICAgc2V0PElJPjo6aXRlcmF0b3IgaXQgPSByaWd2YWwubG93ZXJfYm91bmQoSUkoLXUsIGhbdV0pKTsKICAgIGlmIChpdCA9PSByaWd2YWwuZW5kKCkpIHsKICAgICAgICBpdC0tOwogICAgICAgIGlmIChoW3VdK3YgPj0gaXQtPlkpIHsKICAgICAgICAgICAgcmVzICs9IGNhbGModSsxLCAtaXQtPlgsIGl0LT5ZKTsKICAgICAgICAgICAgcmlndmFsLmluc2VydChJSSgtdSwgaFt1XSt2KSk7CiAgICAgICAgfQogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBNYXhSLCB2dFI7CiAgICBpZiAocmlndmFsLmNvdW50KElJKC11LCBoW3VdKSkpIHsKICAgICAgICBNYXhSID0gaFt1XTsKICAgICAgICB2dFIgPSB1OwogICAgICAgIHJpZ3ZhbC5lcmFzZShJSSgtdSwgaFt1XSkpOwogICAgfQogICAgZWxzZSB7CiAgICAgICAgaXQtLTsKICAgICAgICBpZiAoaFt1XSArIHYgPCBpdC0+WSkgewogICAgICAgICAgICByZXMgLT0gdjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICB2dFIgPSB1OwogICAgICAgIE1heFIgPSBpdC0+WTsKICAgIH0KICAgIHdoaWxlICgxKSB7CiAgICAgICAgaXQgPSByaWd2YWwubG93ZXJfYm91bmQoSUkoLXUsIDApKTsKICAgICAgICBpZiAoaXQgPT0gcmlndmFsLmVuZCgpKSBicmVhazsKICAgICAgICByZXMgLT0gY2FsYygtaXQtPlgrMSwgdnRSLCBNYXhSKTsKCiAgICAgICAgaWYgKGhbdV0rdiA8PSBpdC0+WSkgewogICAgICAgICAgICByZXMgKz0gY2FsYygtaXQtPlgrMSwgdSwgaFt1XSt2KTsKICAgICAgICAgICAgcmVzIC09IHY7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICB2dFIgPSAtaXQtPlg7CiAgICAgICAgTWF4UiA9IGl0LT5ZOwogICAgICAgIHJpZ3ZhbC5lcmFzZShpdCk7CiAgICB9CiAgICByaWd2YWwuaW5zZXJ0KElJKC11LCBoW3VdK3YpKTsKfQoKaW50IG1haW4oKQp7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIC8vZnJlb3BlbigiaW5wLnR4dCIsICJyIiwgc3RkaW4pOwogICAgLy9mcmVvcGVuKCJvdXQudHh0IiwgInciLCBzdGRvdXQpOwogICAgaW50IHRlOwogICAgc2NhbmYoIiVkIiwgJnRlKTsKICAgIHdoaWxlICh0ZS0tKSB7CiAgICAgICAgc2NhbmYoIiVkIiwgJm4pOwogICAgICAgIHNjYW5mKCIlZCIsICZtKTsKICAgICAgICBtcyhzdW0sIDApOwogICAgICAgIEZPUihpLDEsbikgewogICAgICAgICAgICBzY2FuZigiJWQiLCAmaFtpXSk7CiAgICAgICAgICAgIHVwZGF0ZShpLCBoW2ldKTsKICAgICAgICB9CiAgICAgICAgc2NhbmYoIlxuIik7CiAgICAgICAgaW50IE1heEwgPSAwLCB2dEwgPSAwOwogICAgICAgIHJlcyA9IDA7CiAgICAgICAgbGVmdmFsLmNsZWFyKCk7CiAgICAgICAgcmlndmFsLmNsZWFyKCk7CiAgICAgICAgRk9SKGksMSxuKQogICAgICAgICAgICBpZiAoaFtpXSA+IE1heEwpIHsKICAgICAgICAgICAgICAgIHJlcyArPSBjYWxjKHZ0TCwgaS0xLCBNYXhMKTsKICAgICAgICAgICAgICAgIE1heEwgPSBoW2ldOwogICAgICAgICAgICAgICAgdnRMID0gaTsKICAgICAgICAgICAgICAgIGxlZnZhbC5pbnNlcnQoSUkoaSxoW2ldKSk7CiAgICAgICAgICAgIH0KICAgICAgICBpbnQgTWF4UiA9IDAsIHZ0UiA9IG4rMTsKICAgICAgICBGT1JFKGksbiwxKQogICAgICAgICAgICBpZiAoaFtpXSA+PSBNYXhSKSB7CiAgICAgICAgICAgICAgICByZXMgKz0gY2FsYyhpKzEsIHZ0UiwgTWF4Uik7CiAgICAgICAgICAgICAgICBNYXhSID0gaFtpXTsKICAgICAgICAgICAgICAgIHZ0UiA9IGk7CiAgICAgICAgICAgICAgICByaWd2YWwuaW5zZXJ0KElJKC1pLGhbaV0pKTsKICAgICAgICAgICAgfQogICAgICAgIHdoaWxlIChtLS0pIHsKICAgICAgICAgICAgY2hhciBjaDsgaW50IHUsIHY7CiAgICAgICAgICAgIHNjYW5mKCIlYyIsICZjaCk7CiAgICAgICAgICAgIGlmIChjaCA9PSAnUCcpIHsKICAgICAgICAgICAgICAgIHNjYW5mKCJcbiIpOwogICAgICAgICAgICAgICAgcHJpbnRmKCIlSTY0ZFxuIiwgcmVzKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIHNjYW5mKCIlZCIsICZ1KTsKICAgICAgICAgICAgICAgIHNjYW5mKCIlZFxuIiwgJnYpOwogICAgICAgICAgICAgICAgdXBBKHUsIHYpOwogICAgICAgICAgICAgICAgdXBCKHUsIHYpOwogICAgICAgICAgICAgICAgLypwcmludGYoIlxuIik7CiAgICAgICAgICAgICAgICBGT1JBTEwoaXQsIHJpZ3ZhbCkgcHJpbnRmKCIlZCAlZFxuIiwgaXQtPlgsIGl0LT5ZKTsKICAgICAgICAgICAgICAgIHByaW50ZigiXG4iKTsqLwogICAgICAgICAgICAgICAgaFt1XSArPSB2OwogICAgICAgICAgICAgICAgdXBkYXRlKHUsIHYpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0=