#include "nile.h"
#include<bits/stdc++.h>
#define c custo
using namespace std;
const int N = 200010;
long long dp[N];
long long custo[N];
long long w[N];
long long pref[N];
int n;
struct Segtree{
long long tree[4*N];
long long join(long long a, long long b){
return min(a, b);
}
void build(int node, int l, int r){
if(l == r){
tree[node] = 1e18;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void update(int node, int l, int r, int pos, long long val){
if(l == r){
tree[node] = val;
return;
}
int mid = (l+r)/2;
if(l <= pos and pos <= mid)
update(2*node, l, mid, pos, val);
else
update(2*node+1, mid+1, r, pos, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
long long query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r)
return 1e18;
if(l <= tl and tr <= r)
return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg[3];
long long resposta_query[N];
long long calcular_resposta(int l, int r){
long long soma = pref[r] - pref[l-1];
int tam = r-l+1;
////cout << soma << '\n';
if(tam%2 == 0)
return soma;
long long mn = 1e18;
if(l%2 == 0){
mn = seg[1].query(1, l, r, 1, n);
}
else{
mn = seg[0].query(1, l, r, 1, n);
}
mn = min(mn, seg[2].query(1, l, r, 1, n));
////cout << mn << '\n';
return soma - mn;
}
vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
n = W.size();
long long sum = 0;
vector <array <int, 3>> ordenar;
for(int i = 0;i < n;i++){
ordenar.push_back({W[i], A[i], B[i]});
}
vector <pair <int, int>> query;
for(int i = 0;i < E.size();i++){
query.push_back({E[i], i});
}
sort(query.begin(), query.end());
sort(ordenar.begin(), ordenar.end());
for(int i = 0;i < n;i++){
w[i+1] = ordenar[i][0];
sum += (long long) (ordenar[i][1]);
custo[i+1] = ordenar[i][1] - ordenar[i][2];
pref[i+1] = pref[i] + custo[i+1];
}
vector <long long> resposta;
vector <array <long long, 3>> updates;
for(int i = 2;i <= n;i++){
updates.push_back({w[i]-w[i-1], i-1, i});
if(i != n){
updates.push_back({w[i+1]-w[i-1], i-1, i+1});
}
}
seg[0].build(1, 1, n);
seg[1].build(1, 1, n);
seg[2].build(1, 1, n);
for(int i = 1;i <= n;i += 2){
seg[0].update(1, 1, n, i, custo[i]);
}
for(int i = 2;i <= n;i += 2){
seg[1].update(1, 1, n, i, custo[i]);
}
sort(updates.begin(), updates.end());
int ponteiro = 0;
long long ans = 0;
set <pair <int, int>> intervalos;
for(int i = 1;i <= n;i++){
intervalos.insert({i, i});
}
for(auto [d, p1, p2] : updates){
//cout << d << ' ' << ans << '\n';
while(ponteiro < query.size()){
if(d > query[ponteiro].first){
resposta_query[query[ponteiro].second] = sum-ans;
ponteiro++;
}
else
break;
}
if(p1 == p2-1){
auto it = intervalos.lower_bound({p2, 0});
auto [l2, r2] = *it;
it--;
auto [l1, r1] = *it;
if(d == 2){
//cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
}
ans -= calcular_resposta(l1, r1);
ans -= calcular_resposta(l2, r2);
intervalos.erase({l1, r1});
intervalos.erase({l2, r2});
ans += calcular_resposta(l1, r2);
intervalos.insert({l1, r2});
}
else{
int pos = p1+1;
auto it = intervalos.lower_bound({pos, 0});
it--;
auto [l, r] = *it;
ans -= calcular_resposta(l, r);
seg[2].update(1, 1, n, pos, custo[pos]);
ans += calcular_resposta(l, r);
}
}
while(ponteiro < query.size()){
if(true){
resposta_query[query[ponteiro].second] = sum-ans;
ponteiro++;
}
else
break;
}
for(int i = 0;i < E.size();i++)
resposta.push_back(resposta_query[i]);
return resposta;
}
