// first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN reverse replace stringstream string::npos length substr front priority_queue
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#include <bits/stdc++.h>
using namespace std;
#define debug(...) 42
#endif
#define ll long long
#define all(a) (a).begin(),(a).end()
using pll = pair < ll, ll > ;
const ll sz = 8e5 + 10 ;
vector< vector< ll>> tree( sz) ;
vector< vector< ll>> pre( sz) ;
vector< ll> sum( sz) ;
ll curVal;
void merge( ll node, ll x, ll y) {
ll i = 0 , j = 0 ;
tree[ node] .clear ( ) ;
pre[ node] .clear ( ) ;
sum[ node] = 0 ;
while ( i < tree[ x] .size ( ) ) {
tree[ node] .push_back ( tree[ x] [ i] ) ;
i++ ;
}
i = 0 ;
if ( tree[ node] .size ( ) ) i = tree[ node] .back ( ) ;
while ( j < tree[ y] .size ( ) ) {
ll t = max( i, tree[ y] [ j] ) ;
sum[ node] + = t - tree[ y] [ j] ;
tree[ node] .push_back ( t) ;
j++ ;
}
i = j = 0 ;
while ( i < tree[ node] .size ( ) ) {
j + = tree[ node] [ i] ; i++ ;
pre[ node] .push_back ( j) ;
}
}
void update( ll node, ll l, ll r, ll idx, ll val) {
if ( l > r) return ;
if ( l == r) {
tree[ node] = { val} ;
pre[ node] = { val} ;
return ;
}
ll mid = ( l + r) / 2 ;
if ( idx <= mid) update( 2 * node, l, mid, idx, val) ;
else update( 2 * node + 1 , mid + 1 , r, idx, val) ;
merge( node, node * 2 , node * 2 + 1 ) ;
}
ll get( ll node, ll l, ll r, ll rangeL, ll rangeR, ll & val) {
if ( l > r or l > rangeR or r < rangeL) return 0 ;
if ( rangeL <= l and r <= rangeR) {
ll x = sum[ node] ;
if ( tree[ node] .size ( ) ! = 0 ) {
ll i = lower_bound( all( tree[ node] ) , val) - tree[ node] .begin ( ) ;
if ( i > 0 ) x + = ( i * val) - pre[ node] [ i - 1 ] ;
val = max( val, tree[ node] .back ( ) ) ;
}
return x;
}
ll mid = ( l + r) / 2 ;
ll idx = get( node * 2 , l, mid, rangeL, rangeR, val) ;
idx + = get( node * 2 + 1 , mid + 1 , r, rangeL, rangeR, val) ;
return idx;
}
int32_t main( ) {
ios:: sync_with_stdio ( 0 ) ; cin .tie ( 0 ) ; cout .tie ( 0 ) ;
ll t, i, j, y, x, n, z, k;
cin >> n >> t;
vector< ll> val, ans;
for ( ll i = 1 ; i <= n; i++ ) {
cin >> x; val.push_back ( x) ;
update( 1 , 1 , n, i, x) ;
}
while ( t-- ) {
cin >> x >> y;
ll mn = 0 ;
z = get( 1 , 1 , n, x, y, mn) ;
ans.push_back ( z) ;
}
debug( ans) ;
for ( auto & zx : ans) cout << zx << " " ;
}
Ly8gZmlyc3Qgc2Vjb25kIHB1c2hfYmFjayB1bm9yZGVyZWQgcmV0dXJuIGNvbnRpbnVlIGJyZWFrIHZlY3RvciB2aXNpdGVkIGNoZWNrIGZsYWcgYm9vbCB3aGlsZSBpdGVyYXRvciBiZWdpbiBlbmQgbG93ZXJfYm91bmQgdXBwZXJfYm91bmQgdGVtcCB0cnVlIGZhbHNlIGxsX01BWCBsbF9NSU4gaW5zZXJ0IGVyYXNlIGNsZWFyIHBvcCBwdXNoIGNvbXBhcmUgbGw2NF9NQVggbGw2NF9NSU4gIHJldmVyc2UgcmVwbGFjZSBzdHJpbmdzdHJlYW0gc3RyaW5nOjpucG9zIGxlbmd0aCBzdWJzdHIgZnJvbnQgcHJpb3JpdHlfcXVldWUKCiNpZm5kZWYgT05MSU5FX0pVREdFCiNpbmNsdWRlICJkZWJ1Zy5oIgojZWxzZQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBkZWJ1ZyguLi4pIDQyCiNlbmRpZgoKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBhbGwoYSkgICAgICAoYSkuYmVnaW4oKSwoYSkuZW5kKCkKdXNpbmcgcGxsID0gcGFpciA8IGxsLCBsbCA+OwoKY29uc3QgbGwgc3ogPSA4ZTUgKyAxMDsKdmVjdG9yPHZlY3RvcjxsbD4+IHRyZWUoc3opOwp2ZWN0b3I8dmVjdG9yPGxsPj4gcHJlKHN6KTsKdmVjdG9yPGxsPiBzdW0oc3opOwpsbCBjdXJWYWw7Cgp2b2lkIG1lcmdlKGxsIG5vZGUsIGxsIHgsIGxsIHkpIHsKCWxsIGkgPSAwLCBqID0gMDsKCXRyZWVbbm9kZV0uY2xlYXIoKTsKCXByZVtub2RlXS5jbGVhcigpOwoJc3VtW25vZGVdID0gMDsKCgl3aGlsZSAoaSA8IHRyZWVbeF0uc2l6ZSgpKSB7CgkJdHJlZVtub2RlXS5wdXNoX2JhY2sodHJlZVt4XVtpXSk7CgkJaSsrOwoJfQoKCWkgPSAwOwoJaWYgKHRyZWVbbm9kZV0uc2l6ZSgpKQlpID0gdHJlZVtub2RlXS5iYWNrKCk7CgoJd2hpbGUgKGogPCB0cmVlW3ldLnNpemUoKSkgewoJCWxsIHQgPSBtYXgoaSwgdHJlZVt5XVtqXSk7CgkJc3VtW25vZGVdICs9IHQgLSB0cmVlW3ldW2pdOwoJCXRyZWVbbm9kZV0ucHVzaF9iYWNrKHQpOwoJCWorKzsKCX0KCglpID0gaiA9IDA7Cgl3aGlsZSAoaSA8IHRyZWVbbm9kZV0uc2l6ZSgpKSB7CgkJaiArPSB0cmVlW25vZGVdW2ldOwlpKys7CgkJcHJlW25vZGVdLnB1c2hfYmFjayhqKTsKCX0KfQoKdm9pZCB1cGRhdGUobGwgbm9kZSwgbGwgbCwgbGwgciwgbGwgaWR4LCBsbCB2YWwpIHsKCWlmIChsID4gcikJcmV0dXJuOwoJaWYgKGwgPT0gcikgewoJCXRyZWVbbm9kZV0gPSB7dmFsfTsKCQlwcmVbbm9kZV0gPSB7dmFsfTsKCQlyZXR1cm47Cgl9CgoJbGwgbWlkID0gKGwgKyByKSAvIDI7CglpZiAoaWR4IDw9IG1pZCkJdXBkYXRlKDIgKiBub2RlLCBsLCBtaWQsIGlkeCwgdmFsKTsKCWVsc2UJdXBkYXRlKDIgKiBub2RlICsgMSwgbWlkICsgMSwgciwgaWR4LCB2YWwpOwoKCW1lcmdlKG5vZGUsIG5vZGUgKiAyLCBub2RlICogMiArIDEpOwp9CgpsbCBnZXQobGwgbm9kZSwgbGwgbCwgbGwgciwgbGwgcmFuZ2VMLCBsbCByYW5nZVIsIGxsICZ2YWwpIHsKCWlmIChsID4gciBvciBsID4gcmFuZ2VSIG9yIHIgPCByYW5nZUwpCXJldHVybiAwOwoKCWlmIChyYW5nZUwgPD0gbCBhbmQgciA8PSByYW5nZVIpCXsKCQlsbCB4ID0gc3VtW25vZGVdOwoJCWlmICh0cmVlW25vZGVdLnNpemUoKSAhPSAwKSB7CgkJCWxsIGkgPSBsb3dlcl9ib3VuZChhbGwodHJlZVtub2RlXSksIHZhbCkgLSB0cmVlW25vZGVdLmJlZ2luKCk7CgkJCWlmIChpID4gMCkJeCArPSAoaSAqIHZhbCkgLSBwcmVbbm9kZV1baSAtIDFdOwoJCQl2YWwgPSBtYXgodmFsLCB0cmVlW25vZGVdLmJhY2soKSk7CgkJfQoJCXJldHVybiB4OwoJfQoKCWxsIG1pZCA9IChsICsgcikgLyAyOwoJbGwgaWR4ID0gZ2V0KG5vZGUgKiAyLCBsLCBtaWQsIHJhbmdlTCwgcmFuZ2VSLCB2YWwpOwoJaWR4ICs9IGdldChub2RlICogMiArIDEsIG1pZCArIDEsIHIsIHJhbmdlTCwgcmFuZ2VSLCB2YWwpOwoJcmV0dXJuIGlkeDsKfQoKCmludDMyX3QgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKDApOyAJCWNpbi50aWUoMCk7IGNvdXQudGllKDApOwoKCWxsIHQsIGksIGosIHksIHgsIG4sIHosIGs7CgljaW4gPj4gbiA+PiB0OwoJdmVjdG9yPGxsPiB2YWwsIGFuczsKCglmb3IgKGxsIGkgPSAxOyBpIDw9IG47IGkrKykgewoJCWNpbiA+PiB4Owl2YWwucHVzaF9iYWNrKHgpOwoJCXVwZGF0ZSgxLCAxLCBuLCBpLCB4KTsKCX0KCgl3aGlsZSAodC0tKSB7CgkJY2luID4+IHggPj4geTsKCQlsbCBtbiA9IDA7CgkJeiA9IGdldCgxLCAxLCBuLCB4LCB5LCBtbik7CgkJYW5zLnB1c2hfYmFjayh6KTsKCX0KCglkZWJ1ZyhhbnMpOwoJZm9yIChhdXRvICZ6eCA6IGFucykJY291dCA8PCB6eCA8PCAiICI7Cn0KCg==