#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 7.5e5 + 5;
const ll linf = 0x3f3f3f3f3f3f3f3f;

struct Line
{
	ll k,b;
	ll get(ll x) const { return k * x + b;}
};

struct Segment_Tree
{
	Line tree[MAXN<<2];
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
	#define lson(u) ls(u),l,mid
	#define rson(u) rs(u),mid+1,r
	void build(int u,int l,int r)
	{
		tree[u] = {0, linf};
		if(l == r) return;
		int mid = (l+r)>>1;
		build(lson(u)); build(rson(u));
	}
	void insert(int u,int l,int r,int ql,int qr,Line k)
	{
		int mid = (l+r)>>1;
		if(ql<=l && r<=qr)
		{
			if(tree[u].get(mid) > k.get(mid)) swap(tree[u], k);
			if(l == r) return;
			if(tree[u].get(l) > k.get(l))
				insert(lson(u),ql,qr,k);
			if(tree[u].get(r) > k.get(r))
				insert(rson(u),ql,qr,k);
		}
		else
		{
			if(ql<=mid) insert(lson(u),ql,qr,k);
			if(mid<qr) insert(rson(u),ql,qr,k);
		}
	}
	ll query(int u,int l,int r,int q)
	{
		ll res = tree[u].get(q);
		if(l == r) return res;
		int mid = (l+r)>>1;
		return min(res, q<=mid? query(lson(u),q): query(rson(u),q));
	}
}tree;

vector<ll> solve(vector<int> a, vector<int> ql, vector<int> qr)
{
	int n = (int)a.size(), Q = (int)ql.size();
	a.insert(a.begin(), 0);
	for(auto &t: ql)
		++t;
	for(auto &t: qr)
		++t;
	
	static vector<int> eff[MAXN];
	for(int i=1; i<=n; ++i)
		eff[i].clear();
	for(int i=0; i<Q; ++i)
		eff[qr[i]].emplace_back(i);
	
	vector<ll> res(Q);
	
	static ll f[MAXN], g[MAXN];
	static int siz[MAXN], rig[MAXN];
	
	static int sta[MAXN];
	int tp = 0;
	for(int i=1; i<=n; ++i)
	{
		siz[i] = 0; f[i] = 0;
		while(tp && a[sta[tp]] < a[i])
		{
			int j = sta[tp--];
			rig[j] = i;
			f[i] = min(f[j] + (ll)a[j] * siz[i], f[i] + (ll)a[j] * siz[j]);
			siz[i] += siz[j];
		}
		f[i] += a[i]; siz[i] += 1;
		rig[i] = n+1;
		sta[++tp] = i;
		
		if(tp == 1) g[i] = 0;
		else
		{
			int j = sta[tp-1];
			g[i] = g[j] + (ll)a[j] * siz[j];
		}
		
		for(int j: eff[i])
		{
			int pos = lower_bound(sta+1, sta+tp+1, ql[j]) - sta;
			if(pos == tp)
			{
				int mid = sta[pos];
				res[j] = (ll)a[mid] * (mid - ql[j] + 1);
				ql[j] = qr[j] + 1;
			}
			else
			{
				int k = sta[pos+1], mid = sta[pos];
				res[j] = - g[k] + (ll)a[mid] * (mid - ql[j] + 1);
				ql[j] = mid + 1;
			}
		}
	}
	
	for(int i=1; i<=n; ++i)
		eff[i].clear();
	for(int i=0; i<Q; ++i)
		if(ql[i] <= qr[i])
			eff[ql[i]].emplace_back(i);
	
	tree.build(1,1,n);
	for(int i=n; i>=1; --i)
	{
		tree.insert(1,1,n, i, rig[i] - 1, Line{(ll)a[i], f[i] + g[i] - (ll)i * a[i]});
		for(int j: eff[i])
		{
			res[j] += tree.query(1,1,n, qr[j]);
		}
	}
	
	return res;
}

vector<ll> minimum_costs(vector<int> a, vector<int> ql, vector<int> qr)
{
	auto res = solve(a, ql, qr);
	
	reverse(a.begin(), a.end());
	for(auto &t: ql)
		t = (int)a.size() - t - 1;
	for(auto &t: qr)
		t = (int)a.size() - t - 1;
	swap(ql, qr);
	
	auto res2 = solve(a, ql, qr);
	for(int i=0; i<(int)res.size(); ++i)
		res[i] = min(res[i], res2[i]);
	return res;
}