#include <bits/stdc++.h>
using namespace std;
int N;
int A[200001];
int LG[200001], SP[18][200001], MAX[18][200001], MIN[18][200001];
inline void Setup()
{
for(int i = 2; i <= N; i++) LG[i] = LG[i - 1] + !(i & (i - 1));
for(int i = 1; i <= N; i++) SP[0][i] = i;
for(int j = 1; (1 << j) < N; j++)
{
for(int i = 1; (i + (1 << j) - 1) <= N; i++) SP[j][i] = (A[SP[j - 1][i]] > A[SP[j - 1][i + (1 << (j - 1))]]) ? SP[j - 1][i] : SP[j - 1][i + (1 << (j - 1))];
}
return;
}
inline int Get(int l, int r)
{
int j = LG[r - l + 1];
return (A[SP[j][l]] > A[SP[j][r - (1 << j) + 1]]) ? SP[j][l] : SP[j][r - (1 << j) + 1];
}
void init(int n, vector <int> a)
{
N = n;
for(int i = 1; i <= N; i++) A[i] = a[i - 1];
Setup();
stack <pair <int, int>> S;
for(int i = 1; i <= N; i++)
{
while(S.size() && (S.top().first < A[i])) S.pop();
if(S.size()) MIN[0][i] = S.top().second;
S.push({A[i], i});
}
while(S.size()) S.pop();
for(int i = N; i >= 1; i--)
{
while(S.size() && (S.top().first < A[i])) S.pop();
if(S.size()) MAX[0][i] = S.top().second;
S.push({A[i], i});
}
for(int i = 1; i <= N; i++) if(A[MIN[0][i]] > A[MAX[0][i]]) swap(MIN[0][i], MAX[0][i]);
vector <pair <int, int>> V;
for(int i = 1; i <= N; i++) V.push_back({A[i], i});
sort(V.begin(), V.end(), greater <pair <int, int>>());
for(pair <int, int> p : V)
{
int i = p.second;
for(int j = 1; j <= 17; j++) MIN[j][i] = MIN[j - 1][MIN[j - 1][i]];
for(int j = 1; j <= 17; j++) MAX[j][i] = MAX[j - 1][MAX[j - 1][i]];
}
return;
}
int minimum_jumps(int a, int b, int c, int d)
{
a++, b++, c++, d++;
int ret = INT_MAX;
for(; c <= d; c++)
{
int a1 = a, temp = 0;
if(MIN[0][c] < c) a1 = max(MIN[0][c] + 1, a1);
if(MAX[0][c] < c) a1 = max(MAX[0][c] + 1, a1);
if(a1 > b) continue;
a1 = Get(a1, b);
for(int j = 17; j >= 0; j--) if(MAX[j][a1] && (A[MAX[j][a1]] <= A[c])) {a1 = MAX[j][a1]; temp += 1 << j;}
for(int j = 17; j >= 0; j--) if(MIN[j][a1] && (A[MIN[j][a1]] <= A[c])) {a1 = MIN[j][a1]; temp += 1 << j;}
ret = min(temp, ret);
}
if(ret == INT_MAX) return -1;
return ret;
}
//int main()
//{
// int n;
// cin >> n;
// vector <int> h(n);
// for(int i = 0; i < n; i++) cin >> h[i];
// init(n, h);
// int q, a, b, c, d;
// cin >> q;
// while(q--)
// {
// cin >> a >> b >> c >> d;
// cout << minimum_jumps(a, b, c, d) << '\n';
// }
//
// return 0;
//}
