#include <bits/stdc++.h>
using namespace std;
const int mxN = 205;
bool sub1 = false;
vector<int> height;
int precomp[mxN][mxN];
int bfs(int i, int end) {
int n = int(height.size());
queue<pair<int, int> > q;
q.push({i, 0});
while(!q.empty()) {
int u = q.front().first, jumps = q.front().second;
q.pop();
if(u == end)
return jumps;
if(height[u] > height[end]) continue;
int j = u;
while(j >= 0 && height[j] <= height[u])
j--;
// cout << "bfs_1: " << u << " " << j << " " << jumps+1 << "\n";
if(j >= 0)
q.push({j, jumps+1});
j = u;
while(j < n && height[j] <= height[u])
j++;
// cout << "bfs_2: " << u << " " << j << " " << jumps+1 << "\n";
if(j < n)
q.push({j, jumps+1});
}
return -1;
}
void init(int n, vector<int> h) {
if(is_sorted(h.begin(), h.end()))
sub1 = true;
height = h;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
precomp[i][j] = INT_MAX;
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
if(height[j] < height[i]) continue;
int jumps = bfs(i, j);
if(jumps != -1)
precomp[i][j] = min(precomp[i][j], jumps);
}
}
}
int minimum_jumps(int a, int b, int c, int d) {
if(sub1)
return c-b;
else {
int ans = INT_MAX;
for(int i = a; i <= b; i++) {
for(int j = c; j <= d; j++)
ans = min(ans, precomp[i][j]);
}
if(ans == INT_MAX)
return -1;
return ans;
}
}
/*
int main() {
int n = 7;
vector<int> h = {3, 2, 1, 6, 4, 5, 7};
init(n, h);
int a = 0, b = 1, c = 2, d = 2;
printf("%d\n", minimum_jumps(a, b, c, d));
return 0;
}
*/
/*
0 1 2 3 4 5 6
3 2 1 6 4 5 7
(1, 3)
(5, 6)
*/
