#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
ll tab[N], l[N];
int drz[2 * N], lazy[2 * N];
pair<pair<int, int>, int> que[N];
ll answer[N];
void Add(int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
++drz[v]; ++lazy[v];
return;
}
Add(v * 2, p, (p + k) / 2, pz, kz);
Add(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
drz[v] = max(drz[v * 2], drz[v * 2 + 1]) + lazy[v];
}
int Query(int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return 0;
if(p >= pz && k <= kz)
return drz[v];
int ans;
ans = Query(v * 2, p, (p + k) / 2, pz, kz);
ans = max(ans, Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz));
return ans + lazy[v];
}
void DoQ(int n, int q)
{
int j = q + 1, l = n;
sort(que + 1, que + 1 + q);
for(int i = n; i >= 1; --i)
{
if(tab[i] == 2)
l = i - 1;
if(tab[i] == 1)
Add(1, 0, N - 1, i, l);
while(que[j - 1].st.st == i)
{
--j;
int x = Query(1, 0, N - 1, que[j].st.st, que[j].st.nd), d = que[j].st.nd - que[j].st.st + 1;
//cerr << l << " " << "query: " << i << " " << x << " " << d << "\n";
answer[que[j].nd] = 2 * d - x;
}
}
}
ll Ans(int a, int b)
{
ll ans = I;
vector<pair<ll, int>> kol;
kol.pb(make_pair(I, a - 1));
ll s = 0LL;
l[a - 1] = 0LL;
for(int i = a; i <= b; ++i)
{
while(kol.back().st <= tab[i])
{
int r = (int)kol.size() - 1;
s -= (ll)(kol[r].nd - kol[r - 1].nd) * kol[r].st;
kol.pop_back();
}
s += (ll)(i - kol.back().nd) * tab[i];
kol.pb(make_pair(tab[i], i));
l[i] = s;
}
kol.clear();
kol.pb(make_pair(I, b + 1));
s = 0LL;
for(int i = b; i >= a; --i)
{
while(kol.back().st <= tab[i])
{
int r = (int)kol.size() - 1;
s -= (ll)(kol[r - 1].nd - kol[r].nd) * kol[r].st;
kol.pop_back();
}
s += (ll)(kol.back().nd - i) * tab[i];
ans = min(l[i] - tab[i] + s, ans);
kol.pb(make_pair(tab[i], i));
}
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
vector<ll> ans;
int n = H.size(), q = L.size();
for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
for(int i = 1; i <= q; ++i)
que[i] = make_pair(make_pair(L[i - 1] + 1, R[i - 1] + 1), i);
if(n > 50000)
{
DoQ(n, q);
for(int i = 1; i <= q; ++i)
ans.pb(answer[i]);
return ans;
}
for(int i = 1; i <= q; ++i)
ans.pb(Ans(que[i].st.st, que[i].st.nd));
return ans;
}
