#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie() , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define int long long
#define MAX 300900
#define INF 10000000000090LL
#define ls (now << 1)
#define rs (now << 1 | 1)
#define mid ((l + r) >> 1)

int n , m;
int x[MAX] , sml[MAX * 4] , sec[MAX * 4] , sum[MAX * 4] , cnt[MAX * 4];
void Pull(int now , int l , int r){
    sum[now] = sum[ls] + sum[rs];

    sml[now] = min(sml[ls] , sml[rs]);

    cnt[now] = 0;
    if(sml[now] == sml[ls]) cnt[now] += cnt[ls];
    if(sml[now] == sml[rs]) cnt[now] += cnt[rs];

    sec[now] = min(sec[ls] , sec[rs]);
    if(sml[now] != sml[ls]) sec[now] = min(sec[now] , sml[ls]);
    if(sml[now] != sml[rs]) sec[now] = min(sec[now] , sml[rs]);

}
void Push(int now , int l , int r){
    if(l == r) return;
    if(sml[ls] < sml[now]){
        if(sml[now] < sec[ls]){
            sum[ls] += (sml[now] - sml[ls]) * cnt[ls];
            sml[ls] = sml[now];
        }
        else Push(ls , l , mid);
    }
    if(sml[rs] < sml[now]){
        if(sml[now] < sec[rs]){
            sum[rs] += (sml[now] - sml[rs]) * cnt[rs];
            sml[rs] = sml[now];
        }
        else Push(rs , mid + 1 , r);
    }
}
void update(int now , int l , int r , int ql , int qr , int val){
    if(val <= sml[now]) return;
    Push(now , l , r);
    if(ql <= l && r <= qr){
        if(l == r) cnt[now] = 1 , sec[now] = INF;
        if(val < sec[now]){
            sum[now] += (val - sml[now]) * cnt[now];
            sml[now] = val;
        }
        else{
            update(ls , l , mid , ql , qr , val);
            update(rs , mid + 1 , r , ql , qr , val);
            Pull(now , l , r);
        }
        return;
    }
    if(ql <= mid) update(ls , l , mid , ql , qr , val);
    if(mid + 1 <= qr) update(rs , mid + 1 , r , ql , qr , val);
    Pull(now , l , r);
}
int query(int now , int l , int r , int ql , int qr){
    Push(now , l , r);
    if(ql <= l && r <= qr) return sum[now];
    if(qr <= mid) return query(ls , l , mid , ql , qr);
    if(mid + 1 <= ql) return query(rs , mid + 1 , r , ql , qr);
    return query(ls , l , mid , ql , qr) + query(rs , mid + 1 , r , ql , qr);
}
int32_t main(){
    IOS;
    cin >> n >> m;
    REP(i , 1 , n + 1) cin >> x[i];
    REP(i , 1 , n + 1) update(1 , 1 , n , i , i , x[i]);

    REP(i , 1 , m + 1){
        int ty , l , r , v;
        cin >> ty;
        if(ty == 1){
            cin >> l >> r >> v;
            update(1 , 1 , n , l , r , v);
        }
        else{
            cin >> l >> r;
            cout << query(1 , 1 , n , l , r) << endl;
        }
    }

    return 0;
}