#include "meetings.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
#define ALL(x) begin(x), end(x)
int np2(int n) {
int N = 1;
while (N < n) N *= 2;
return N;
}
const ll maxh = 20;
struct Node {
ll mx = -1e18;
ll very_best = 1e18;
ll best[maxh][maxh]{};
ll lstart[maxh]{};
ll rstart[maxh]{};
Node() {
for (int h = 0; h < maxh; h++) {
this->lstart[h] = 0;
this->rstart[h] = 0;
for (int h2 = 0; h2 < maxh; h2++) {
this->best[h][h2] = 1e18;
}
}
}
Node(int x) {
this->mx = x;
this->very_best = x;
for (int h = 0; h < maxh; h++) {
this->lstart[h] = max(h, x);
this->rstart[h] = max(h, x);
for (int h2 = 0; h2 < maxh; h2++) {
this->best[h][h2] = 1e18;
}
}
this->best[x][x] = x;
}
};
Node merge(Node a, Node b) {
Node r{};
r.mx = max(a.mx, b.mx);
for (int h = 0; h < maxh; h++) {
for (int h2 = 0; h2 < maxh; h2++) {
r.best[h][h2] = 1e18;
}
}
for (ll h = 0; h < maxh; h++) {
r.lstart[h] = a.lstart[h] + b.lstart[min(max(h, a.mx), maxh-1)];
r.rstart[h] = b.rstart[h] + a.rstart[min(max(h, b.mx), maxh-1)];
for (ll h2 = 0; h2 < maxh; h2++) {
r.best[h][min(max(h2, b.mx), maxh-1)] = min(r.best[h][min(max(h2, b.mx), maxh-1)], a.best[h][h2] + b.lstart[h2]);
r.best[min(max(h2, a.mx), maxh-1)][h] = min(r.best[min(max(h2, a.mx), maxh-1)][h], b.best[h2][h] + a.rstart[h2]);
}
}
r.very_best = 1e18;
for (int h = 0; h < maxh; h++) {
for (int h2 = 0; h2 < maxh; h2++) {
r.very_best = min(r.best[h][h2], r.very_best);
}
}
return r;
}
vector<Node> tree;
Node query(int l, int r, int a, int b, int k) {
if (a > r || b < l) return {};
if (a >= l && b <= r) return tree[k];
int m = (a+b)/2;
return merge(query(l, r, a, m, 2*k), query(l, r, m+1, b, 2*k+1));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
for (int& x : H) x--;
int n = H.size();
int Q = L.size();
std::vector<long long> C(Q);
int N = np2(n);
tree.assign(2*N, {});
for (int i = 0; i < n; i++) tree[N+i] = Node(H[i]);
for (int i = N-1; i > 0; i--) tree[i] = merge(tree[2*i], tree[2*i+1]);
for (int i = 0; i < Q; i++) C[i] = query(L[i], R[i], 0, N-1, 1).very_best + R[i] - L[i]+1;
return C;
}
/*
4 2
2 4 3 5
0 2
1 3
4 1
2 4 3 5
1 3
*/
