#include "meetings.h"
#include <iostream>
#include <vector>
#include "meetings.h"
#include <iostream>
using namespace std;
typedef long long ll;
// #define ll ll
#define Data pair<ll,ll>
const ll LG=20,inf=2e9,N=1e6+10;
Data sp[N][LG];
ll ans[N],pre[N];
ll a[N];
vector<vector<ll>> qry[N];
ll get(ll ql,ll qr)
{
qr++;
Data cur={-inf,0};
for(ll j=LG-1;j>=0;j--)
{
if((ql+(1<<j))<=qr)
{
cur=max(cur,sp[ql][j]);
ql+=(1<<j);
}
}
return -cur.second;
}
void solve(ll l,ll r)
{
if(l>r)return;
ll m=get(l,r);
solve(l,m-1);
solve(m+1,r);
for(auto cq:qry[m])
{
ll l=cq[0],r=cq[1],ind=cq[2];
ans[ind]=min(ans[ind],pre[r]+1ll*(m-l+1)*a[m]);
}
pre[m]=a[m]+((m>l)?pre[m-1]:0);
for(ll i=m+1;i<=r;i++)pre[i]=min(pre[m]+1ll*(i-m)*a[m],pre[i]+1ll*(m-l+1)*a[m]);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,vector<int> r) {
ll n=h.size(),q=l.size();
for(ll i=0;i<=q;i++)ans[i]=1e18;
for(ll i=0;i<=n;i++)
{
pre[i]=0;
if(i)a[i]=h[i-1];
qry[i].clear();
sp[i][0]={h[i-1],-i};
}
for(ll j=1;j<LG;j++)
{
for(ll i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(ll i=0;i<q;i++)
{
l[i]++;
r[i]++;
ll m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
for(ll i=0;i<=n;i++)
{
if(i)a[i]=h[n-i];
qry[i].clear();
sp[i][0]={a[i],-i};
pre[i]=0;
}
for(ll j=1;j<LG;j++)
{
for(ll i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(ll i=0;i<q;i++)
{
swap(l[i],r[i]);
l[i]=n-l[i]+1;
r[i]=n-r[i]+1;
ll m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
vector<long long> fnl;
for(ll i=0;i<q;i++)
{
fnl.push_back(ans[i]);
}
return fnl;
}
// int main()
// {
// int n,q;
// cin>>n>>q;
// vector<int> a(n),l(q),r(q);
// for(int i=0;i<n;i++)cin>>a[i];
// for(int i=0;i<q;i++)cin>>l[i]>>r[i];
// for(auto x:minimum_costs(a,l,r))
// {
// cout<<x<<endl;
// }
// }
