// 100 p
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#ifdef LOCAL_RUN
#include "prettyprint.hpp"
#endif // LOCAL_RUN
#define debug(x) do{}while(0)
using namespace std;
using ll = long long;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1e9;
// could maybe be optimized by transposing
template<typename T = int, typename comp = greater<T>>
class Sparsetable{
int compind(int i, int j, int l, int sign)const{
i = RMQ[lgn*i+l], j=RMQ[lgn*(j+sign*(1<<l))+l];
return comp()(data[i], data[j])? i : j;
}
int minind(int l, int r)const{
assert(l<r);
return compind(l, r, lg2[r-l],-1);
}
void build(){
lg2.resize(n+1);
for(int i=2;i<=n;++i) lg2[i]=1+lg2[i/2];
lgn = lg2.back()+1;
RMQ.resize(n*lgn);
for(int i=n-1;i>=0;--i){
RMQ[lgn*i]=i;
for(int j=0;j<lg2[n-i];++j) RMQ[lgn*i+j+1] = compind(i,i,j,1);
}
}
public:
Sparsetable(T const*v, int _N):n(_N), data(v, v+_N){build();}
Sparsetable(vector<T> const&v):Sparsetable(v.data(), v.size()){};
// min in [l, r)
pair<int, T&> operator()(int const&i, int const&j){
int k = minind(i, j);
return pair<int, T&>(k, data[k]);
}
int n, lgn;
vector<int> RMQ, lg2;
vector<T> data;
};
struct Node{
int l_size, r_size;
pair<int, int> val;
ll l_dp, r_dp, dp;
int get_size(){return l_size + r_size + 1;}
void recalc_dp(){
ll cand1 = l_dp + (r_size+1)*(ll)val.first;
ll cand2 = r_dp + (l_size+1)*(ll)val.first;
dp = min(cand1, cand2);
}
};
int n, q;
vector<pair<int, int> > calc_maxval(vector<pair<int, int>> const&H, vector<int> const&L, vector<int> const&R){
Sparsetable<pair<int, int> > s(H);
vector<pair<int, int>> ret(q);
for(int i=0;i<q;++i){
ret[i] = s(L[i], R[i]+1).second;
}
return ret;
}
struct Block{
struct Node{
pair<int, int> val;
ll dp_base;
int l_size;
ll l_add() const {
return (l_size+1)*(ll)val.first;
}
bool operator<(pair<int, int> const&o) const {
return val < o;
}
bool operator>(pair<int, int> const&o) const {
return val > o;
}
friend ostream& operator<<(ostream&o, Node const&n){
#ifdef LOCAL_RUN
return o << n.val << " " << n.dp_base << " " << n.l_size;
#else
return o;
#endif
}
};
deque<Node> nodes;
ll a, b;// globally add a*x+b
// returns (r_dp of max, index of max)
Block(){}
Block(Node const&n, ll a_, ll b_):nodes(1, n), a(a_), b(b_){}
pair<ll, int> query(pair<int, int> const&val, int t){
debug(cerr << "Query " << (*this) << " " << val << " " << t << "\n");
auto it = lower_bound(nodes.begin(), nodes.end(), val, std::greater<>());
assert(it != nodes.end() && it->val == val);
const int index = it->val.second;
++it;
// dp_r is in next block
if(it == nodes.end()){
return make_pair(-1, index);
}
return make_pair(it->dp_base + a*t + b, index);
}
ll query_dp_r(int t){
const Node& n = nodes.front();
return n.dp_base + a*t + b;
}
// TODO: fix
static Block merge(Block &&l, Block &&r){
// make l's dp depend on r
const Node& n1 = l.nodes.back(), n2 = r.nodes.front();
ll l_new_add = -n1.dp_base + n2.dp_base + n1.l_add() - l.b + r.b;
l.b += l_new_add;
l.a = r.a;
// update dp at back
Block *a = &l, *b = &r;
if(a->nodes.size() > b->nodes.size()){
swap(a, b);
}
for(auto &e:a->nodes){
e.dp_base += (a->b - b->b);
}
a->b = b->b;
if(l.nodes.size() < r.nodes.size()){
r.nodes.insert(r.nodes.begin(), l.nodes.begin(), l.nodes.end());
return move(r);
} else {
l.nodes.insert(l.nodes.end(), r.nodes.begin(), r.nodes.end());
return move(l);
}
}
// returns (index, dp)
pair<int, ll> intersect(pair<int, int> const&val, int dir){
pair<int, ll> ret(-1, -1);
while(!nodes.empty() && nodes.back().val <= val){
const int index = nodes.back().val.second;
ret = make_pair(index-dir*nodes.back().l_size, nodes.back().dp_base + a*(val.second-dir) + b);
nodes.pop_back();
}
return ret;
}
int calc_intersection(Block const&r, bool const& rev){
const ll m1 = a, q1 = nodes.back().dp_base + b;
const ll m2 = r.a, q2 = r.nodes.front().dp_base + r.b + nodes.back().l_add();
debug(cerr << "intersect " << m1 << " " << q1 << " | " << m2 << " " << q2 << "\n");
if(m1 == m2){
if(q2 <= q1){ // already intersected
return rev ? inf : -inf;
} else { // won't ever intersect
return rev ? -inf : inf;
}
} else {
// intersection at (q2-q1)/(m1-m2) -> round correctly
long double tmp = (q2 - q1) / (long double)(m1 - m2);
if(tmp < -inf) return -inf;
if(tmp > inf) return inf;
return rev ? floor(tmp) : ceil(tmp);
}
}
friend ostream& operator<<(ostream&o, Block const&b){
#ifdef LOCAL_RUN
return o << "Block: " << b.a << "*x + " << b.b << " : " << b.nodes;
#else
return o;
#endif
}
};
vector<pair<int, ll> > sweep(vector<pair<int, int>> const&H, vector<pair<int, int>> const&M, vector<int> const&R, bool const rev){
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
const int dir = rev ? -1 : 1;
if(rev){
reverse(ord.begin(), ord.end());
}
vector<vector<int> > ev(n);
for(int i=0;i<q;++i){
ev[R[i]].push_back(i);
}
map<pair<int, int>, Block> s;
vector<pair<int, ll> > ret(q);
min_heap<array<int, 3> > inters;
auto add_event = [&](map<pair<int, int>, Block>::iterator it){
assert(it != s.end());
auto it2 = next(it);
if(it2 == s.end()) return;
int inter = it2->second.calc_intersection(it->second, rev);
inters.push({inter*dir, it->first.first, it->first.second});
};
for(auto const&e:ord){
// add element to cartesian tree
Block::Node n{H[e], 0, 0};
auto it = s.begin();
for(;it != s.end();++it){
auto tmp = it->second.intersect(H[e], dir);
if(tmp.first == -1 && tmp.second == -1){
break;
}
n.l_size = abs(e - tmp.first);
n.dp_base = tmp.second;
}
if(it != s.begin()){
--it;
s.erase(s.begin(), it);
if(it->second.nodes.empty()) s.erase(it);
}
s[H[e]] = Block(n, n.val.first*dir, -n.val.first*dir * (ll)n.val.second + n.val.first);
add_event(s.begin());
// process intersection events
while(!inters.empty() && inters.top()[0] <= dir*e){
auto inter = inters.top();
inters.pop();
pair<int, int> l = make_pair(inter[1], inter[2]);
auto it = s.find(l);
if(it == s.end()) continue;
auto it2 = next(it);
if(it2 == s.end()) continue;
int real_inter = it2->second.calc_intersection(it->second, rev);
if(inter[0] != real_inter*dir) continue;
it2->second = Block::merge(move(it2->second), move(it->second));
s.erase(it);
add_event(it2);
}
debug(cerr << e << " : " << s << "\n");
// process queries
for(auto const&f : ev[e]){
auto it = s.lower_bound(M[f]);
assert(it != s.end());
pair<ll, int> ans = it->second.query(M[f], e);
if(ans.first == -1){
if(it == s.begin()){
ans.first = 0;
} else {
ans.first = prev(it)->second.query_dp_r(e);
}
}
ret[f] = make_pair(abs(e-ans.second), ans.first);
}
//cerr << inters << "\n";
}
debug(cerr << "sweep\n" << R << "\n" << M << "\n" << ret << "\n");
return ret;
}
vector<pair<int, ll> > sweep_slow(vector<pair<int, int>> const&H, vector<pair<int, int>> const&M, vector<int> const&R, bool const rev){
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
if(rev){
reverse(ord.begin(), ord.end());
}
vector<vector<int> > ev(n);
for(int i=0;i<q;++i){
ev[R[i]].push_back(i);
}
vector<Node> s;
vector<pair<int, ll> > ret(q);
for(auto const&e:ord){
// add element to cartesian tree
Node n{0, 0, H[e], 0, 0, H[e].first};
while(!s.empty() && n.val >= s.back().val){
n.l_size = s.back().get_size();
n.l_dp = s.back().dp;
s.pop_back();
}
n.recalc_dp();
s.push_back(n);
for(auto it = s.rbegin(), it2=next(it);it2!=s.rend();it = it2, it2 = next(it)){
++(it2->r_size);
it2->r_dp = it->dp;
it2->recalc_dp();
}
// process queries
for(auto const&f : ev[e]){
int i=0;
while(s[i].val > M[f]) ++i;
assert(s[i].val == M[f]);
ret[f] = make_pair(s[i].r_size, s[i].r_dp);
}
}
//cerr << "sweep\n" << R << "\n" << M << "\n" << ret << "\n";
return ret;
}
vector<ll> minimum_costs(vector<int> HH, vector<int> L, vector<int> R){
assert(L.size() == R.size());
n = HH.size();
q = R.size();
vector<pair<int, int> > H(n);
for(int i=0;i<n;++i){
H[i] = make_pair(HH[i], i);
}
const vector<pair<int, int> > M = calc_maxval(H, L, R);
vector<pair<int, ll> > cost_R = sweep(H, M, R, false);
vector<pair<int, ll> > cost_L = sweep(H, M, L, true);
vector<ll> ret(q);
for(int i=0;i<q;++i){
ll cand1 = M[i].first*(ll)(R[i]-L[i]+1-cost_L[i].first) + cost_L[i].second;
ll cand2 = M[i].first*(ll)(R[i]-L[i]+1-cost_R[i].first) + cost_R[i].second;
debug(cerr << cand1 << " / " << cand2 << "\n");
ret[i] = min(cand1, cand2);
}
return ret;
}
