#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e3+10;
const ll inf=1e18;
struct ds {int l,r,id;};
struct node
{
vi lef,rig;
int p_lef=0,p_rig=0;
};
int a[N],n,q,lg[N];
ds Q1[N],Q2[N];
ll ans[N],val1[N],val2[N];
pii spr[22][N*2];
node it[N*4];
void build2()
{
stack<int> st;
st.push(0);
a[0]=a[n+1]=1e9+1;
for (int i=1;i<=n;i++)
{
while (a[i]>=a[st.top()]) st.pop();
val1[i]=val1[st.top()]+(ll)a[i]*(i-st.top());
st.push(i);
}
while (st.size()) st.pop();
st.push(n+1);
for (int i=n;i;i--)
{
while (a[i]>a[st.top()]) st.pop();
val2[i]=val2[st.top()]+(ll)a[i]*(st.top()-i);
st.push(i);
}
int k=-1;
for (int i=1;i<=n;i++)
{
if (i==(i&-i)) k++;
lg[i]=k;
spr[0][i]=mp(a[i],i);
}
for (int i=1;i<=20;i++)
for (int j=1;j<=n;j++) spr[i][j]=max(spr[i-1][j],spr[i-1][j+(1<<(i-1))]);
}
int max_range(int l,int x)
{
int k=lg[x-l+1];
return max(spr[k][l],spr[k][x-(1<<k)+1]).se;
}
ll suf(int x,int l)
{
int id=max_range(l,x);
return val1[x]-val1[id]+a[id]*(id-l+1);
}
ll pre(int x,int r)
{
int id=max_range(x,r);
return val2[x]-val2[id]+a[id]*(r-id+1);
}
ll cost(int l,int r,int mid) {return suf(mid,l)+pre(mid,r)-a[mid]; }
/*ll cost(int l,int r,int mid)
{
ll res=0;
for (int i=l;i<=r;i++)
if (i<=mid) res+=a[max_range(i,mid)];
else res+=a[max_range(mid,i)];
int val=0;
for (int i=mid;i>=l;i--)
{
val=max(val,a[i]);
res+=val;
}
val=a[mid];
for (int i=mid+1;i<=r;i++)
{
val=max(val,a[i]);
res+=val;
}
return res;
}*/
bool cmp(int a1,int b1,int a2,int b2,int a3,int b3)
{
return (ll)(b2-b1)*(a1-a3)>=(ll)(b3-b1)*(a1-a2);
}
void build(int id,int l,int r)
{
if (l==r)
{
it[id].lef.eb(l);
it[id].rig.eb(r);
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
mid=max_range(l,r);
vector<pll> vt; //fi*x+se
for (int i=mid-1;i>=l;i--)
{
ll val=pre(i,r);
int t=i;
while (vt.size() && vt.back().fi>=-a[i])
{
if (vt.back().fi*(i+1)+vt.back().se+a[i]<val) val=vt.back().fi*(i+1)+vt.back().se+a[i],t=it[id].lef.back();
vt.pop_back();
it[id].lef.pop_back();
}
pii line=mp(-a[i],val+a[i]*i); //-a[i]*i+b=val b=val+a[i]*i
while (vt.size()>1 && cmp(vt[(int)vt.size()-2].fi,vt[(int)vt.size()-2].se,vt.back().fi,vt.back().se,line.fi,line.se)) vt.pop_back(),it[id].lef.pop_back();
vt.eb(line);
it[id].lef.eb(t);
}
vt.clear();
for (int i=mid+1;i<=r;i++)
{
ll val=suf(i,l);
int t=i;
while (vt.size() && vt.back().fi<=a[i])
{
if (vt.back().fi*(i-1)+vt.back().se+a[i]<val) val=vt.back().fi*(i-1)+vt.back().se+a[i],t=it[id].rig.back();
vt.pop_back();
it[id].rig.pop_back();
}
pii line=mp(a[i],val-a[i]*i); //a[i]*i+b=val b=val-a[i]*i
while (vt.size()>1 && cmp(vt[(int)vt.size()-2].fi,vt[(int)vt.size()-2].se,line.fi,line.se,vt.back().fi,vt.back().se)) vt.pop_back(),it[id].rig.pop_back();
vt.eb(line);
it[id].rig.eb(t);
}
}
ll get1(int id,int l,int r,int u,int v)
{
if (l>v || r<u) return inf;
if (u<=l && r<=v)
{
ll val=cost(u,v,it[id].lef[it[id].p_lef]);
while (it[id].p_lef<(int)it[id].lef.size()-1)
{
ll new_val=cost(u,v,it[id].lef[it[id].p_lef+1]);
if (val<new_val) break;
val=new_val;
it[id].p_lef++;
}
return val;
}
int mid=(l+r)/2;
return min(get1(id*2,l,mid,u,v),get1(id*2+1,mid+1,r,u,v));
}
ll get2(int id,int l,int r,int u,int v)
{
if (l>v || r<u) return inf;
if (u<=l && r<=v)
{
ll val=cost(u,v,it[id].rig[it[id].p_rig]);
while (it[id].p_rig<(int)it[id].rig.size()-1)
{
ll new_val=cost(u,v,it[id].rig[it[id].p_rig+1]);
if (val<new_val) break;
val=new_val;
it[id].p_rig++;
}
return val;
}
int mid=(l+r)/2;
return min(get2(id*2,l,mid,u,v),get2(id*2+1,mid+1,r,u,v));
}
bool cmp1(ds t1,ds t2) {return t1.l>t2.l;}
bool cmp2(ds t1,ds t2) {return t1.r<t2.r;}
void process()
{
build2();
for (int i=1;i<=q;i++)
{
int l=Q1[i].l,r=Q1[i].r;
ll res=inf;
for (int t=l;t<=r;t++) res=min(res,cost(l,r,t));
ans[i]=res;
}
/*build(1,1,n);
sort(Q1+1,Q1+n+1,cmp1);
sort(Q2+1,Q2+n+1,cmp2);
for (int i=1;i<=q;i++) ans[i]=inf;
for (int i=1;i<=q;i++) ans[Q1[i].id]=min(ans[Q1[i].id],get1(1,1,n,Q1[i].l,Q1[i].r));
for (int i=1;i<=q;i++) ans[Q2[i].id]=min(ans[Q2[i].id],get2(1,1,n,Q2[i].l,Q2[i].r));*/
}
vll minimum_costs(vi v1,vi v2,vi v3)
{
n=v1.size();
q=v2.size();
for (int i=1;i<=n;i++) a[i]=v1[i-1];
for (int i=1;i<=q;i++) Q1[i]=Q2[i]={v2[i-1]+1,v3[i-1]+1,i};
process();
vll res;
for (int i=1;i<=q;i++) res.eb(ans[i]);
return res;
}
/*int main()
{
freopen("meetings.inp","r",stdin);
freopen("meetings.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
vi v1,v2,v3;
for (int i=1,x;i<=n;i++) cin>>x,v1.eb(x);
for (int i=1,l,r;i<=q;i++) cin>>l>>r,v2.eb(l),v3.eb(r);
vll v4=minimum_costs(v1,v2,v3);
for (ll x : v4) cout<<x<<" ";
return 0;
}*/
