#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Node {
ll first, last; // p[l], p[r]
int len_p; // number of p elements in segment
int d_len; // number of d elements = len_p - 1
ll sum; // total contribution from d runs: sum over runs t*(t+1)/2
int pref; // length of alternating prefix in d (count of d elements)
int suff; // length of alternating suffix in d
int first_sign; // sign of first d element (0 if none)
int last_sign; // sign of last d element (0 if none)
Node() {
first = last = 0;
len_p = d_len = 0;
sum = 0;
pref = suff = 0;
first_sign = last_sign = 0;
}
};
inline int sgnll(ll x){ if(x>0) return 1; if(x<0) return -1; return 0; }
inline ll run_contrib(int t){ return 1LL * t * (t + 1) / 2; }
const int MAXN = 300005;
vector<Node> seg;
vector<ll> lazyAdd;
vector<char> lazyFlip;
int n,q;
vector<ll> a;
Node make_leaf(ll val){
Node nd;
nd.first = nd.last = val;
nd.len_p = 1;
nd.d_len = 0;
nd.sum = 0;
nd.pref = nd.suff = 0;
nd.first_sign = nd.last_sign = 0;
return nd;
}
Node mergeNode(const Node &A, const Node &B){
if(A.len_p == 0) return B;
if(B.len_p == 0) return A;
Node R;
R.len_p = A.len_p + B.len_p;
R.first = A.first;
R.last = B.last;
R.d_len = A.d_len + B.d_len + 1;
ll total = A.sum + B.sum;
int s = sgnll(B.first - A.last);
int left_ext = 0;
if(A.d_len > 0 && A.suff > 0 && A.last_sign != 0 && s != 0 && A.last_sign * s == -1){
left_ext = A.suff;
}
int right_ext = 0;
if(B.d_len > 0 && B.pref > 0 && B.first_sign != 0 && s != 0 && s * B.first_sign == -1){
right_ext = B.pref;
}
if(s != 0){
int combined = left_ext + 1 + right_ext;
if(left_ext > 0) total -= run_contrib(left_ext);
if(right_ext > 0) total -= run_contrib(right_ext);
total += run_contrib(combined);
}
R.sum = total;
if(A.d_len > 0) R.first_sign = A.first_sign;
else {
if(s != 0) R.first_sign = s;
else R.first_sign = B.first_sign;
}
if(B.d_len > 0) R.last_sign = B.last_sign;
else {
if(s != 0) R.last_sign = s;
else R.last_sign = A.last_sign;
}
// pref
if(A.d_len == 0){
if(s == 0){
R.pref = B.pref;
} else {
int ext = 0;
if(B.d_len > 0 && B.pref > 0 && R.first_sign != 0 && R.first_sign * B.first_sign == -1) ext = B.pref;
R.pref = 1 + ext;
}
} else {
if(A.pref == A.d_len && s != 0 && A.last_sign * s == -1){
int ext = 0;
if(B.d_len > 0 && B.pref > 0 && s * B.first_sign == -1) ext = B.pref;
R.pref = A.d_len + 1 + ext;
} else R.pref = A.pref;
}
// suff (fixed logic)
if(B.d_len == 0){
if(s == 0){
R.suff = 0;
} else {
int ext = 0;
if(A.d_len > 0 && A.suff > 0 && A.last_sign * s == -1) ext = A.suff;
R.suff = 1 + ext;
}
} else {
if(B.suff == B.d_len && s != 0 && s * B.first_sign == -1){
int ext = 0;
if(A.d_len > 0 && A.suff > 0 && A.last_sign * s == -1) ext = A.suff;
R.suff = B.d_len + 1 + ext;
} else R.suff = B.suff;
}
return R;
}
void applyAdd(int id, ll v){
lazyAdd[id] += v;
seg[id].first += v;
seg[id].last += v;
// signs and sum/pref/suff unchanged
}
void applyFlip(int id){
lazyFlip[id] ^= 1;
// composition: flip negates pending add
lazyAdd[id] = -lazyAdd[id];
seg[id].first = -seg[id].first;
seg[id].last = -seg[id].last;
// internal d signs are multiplied by -1 => first_sign/last_sign flip sign
seg[id].first_sign = -seg[id].first_sign;
seg[id].last_sign = -seg[id].last_sign;
// sum/pref/suff unchanged (alternation preserved)
}
void pushDown(int id){
int lc = id<<1, rc = lc|1;
if(lc >= (int)seg.size()) return;
if(lazyFlip[id]){
applyFlip(lc);
applyFlip(rc);
lazyFlip[id] = 0;
}
if(lazyAdd[id] != 0){
applyAdd(lc, lazyAdd[id]);
applyAdd(rc, lazyAdd[id]);
lazyAdd[id] = 0;
}
}
void build(int id, int l, int r){
lazyAdd[id] = 0;
lazyFlip[id] = 0;
if(l==r){
seg[id] = make_leaf(a[l]);
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}
void updateAdd(int id, int l, int r, int ql, int qr, ll v){
if(qr<l || r<ql) return;
if(ql<=l && r<=qr){
applyAdd(id, v);
return;
}
pushDown(id);
int mid=(l+r)/2;
updateAdd(id*2,l,mid,ql,qr,v);
updateAdd(id*2+1,mid+1,r,ql,qr,v);
seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}
void updateFlip(int id, int l, int r, int ql, int qr){
if(qr<l || r<ql) return;
if(ql<=l && r<=qr){
applyFlip(id);
return;
}
pushDown(id);
int mid=(l+r)/2;
updateFlip(id*2,l,mid,ql,qr);
updateFlip(id*2+1,mid+1,r,ql,qr);
seg[id] = mergeNode(seg[id*2], seg[id*2+1]);
}
Node queryNode(int id, int l, int r, int ql, int qr){
if(qr<l || r<ql) return Node();
if(ql<=l && r<=qr) return seg[id];
pushDown(id);
int mid=(l+r)/2;
Node L = queryNode(id*2,l,mid,ql,qr);
Node R = queryNode(id*2+1,mid+1,r,ql,qr);
return mergeNode(L,R);
}
inline long long answer_from_node(const Node &nd){
return (long long)nd.len_p + nd.sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin>>n>>q)) return 0;
a.assign(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i];
seg.assign(4*(n+5), Node());
lazyAdd.assign(4*(n+5), 0);
lazyFlip.assign(4*(n+5), 0);
build(1,1,n);
while(q--){
char t; cin>>t;
if(t=='*'){
int l,r; cin>>l>>r;
updateFlip(1,1,n,l,r);
} else if(t=='+'){
int l,r; ll v; cin>>l>>r>>v;
updateAdd(1,1,n,l,r,v);
} else if(t=='?'){
int l,r; cin>>l>>r;
Node nd = queryNode(1,1,n,l,r);
cout << answer_from_node(nd) << '\n';
}
}
return 0;
}
