// CF template, version 3.0
#include <bits/stdc++.h>
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
//#define int long long
vector<pair<int, int>> lpts;
vector<pair<int, int>> rpts;
vector<pair<int, int>> maxima;
vector<vector<pair<int, int>>> greedylift;
vector<vector<pair<int, int>>> rightlift;
vector<vector<int>> sparse;
vector<int> arr;
vector<int> lg;
vector<int> pow2;
map<int, int> ind;
void init(int n, vector<int> nums) {
lpts.resize(n);
rpts.resize(n);
maxima.resize(n);
stack<pair<int, int>> st;
forto(n, i) {
while (!st.empty() && st.top().first < nums[i]) st.pop();
if (st.empty()) lpts[i] = {2e9, -1};
else lpts[i] = {st.top().first, st.top().second};
st.push({nums[i], i});
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.top().first < nums[i]) st.pop();
if (st.empty()) rpts[i] = {2e9, -1};
else rpts[i] = {st.top().first, st.top().second};
st.push({nums[i], i});
}
forto(n, i) maxima[i] = max(lpts[i], rpts[i]);
// Binary lifting.
greedylift.resize(n, vector<pair<int, int>>(19, {2e9, -1}));
rightlift.resize(n, vector<pair<int, int>>(19, {2e9, -1}));
for (int i = n - 1; i >= 0; i--) {
rightlift[i][0] = rpts[i];
for (int j = 1; j < 19; j++) {
if (rightlift[i][j - 1].second == -1) break;
rightlift[i][j] = rightlift[rightlift[i][j - 1].second][j - 1];
}
}
vector<pair<int, int>> sorted;
forto(n, i) sorted.push_back({nums[i], i});
sortl(sorted);
for (int ip = n - 1; ip >= 0; ip--) {
int i = sorted[ip].second;
greedylift[i][0] = maxima[i];
for (int j = 1; j < 19; j++) {
if (greedylift[i][j - 1].second == -1) break;
greedylift[i][j] = greedylift[greedylift[i][j - 1].second][j - 1];
}
}
forto(n, i) arr.push_back(nums[i]), ind[nums[i]] = i;
sparse.resize(n, vector<int>(19, 0));
for (int i = n - 1; i >= 0; i--) {
sparse[i][0] = arr[i];
int power = 1;
for (int j = 1; j < 19; j++) {
power *= 2;
if (i + power > n) break;
sparse[i][j] = max(sparse[i][j - 1], sparse[i + power / 2][j - 1]);
}
}
int logval = -1;
int logpow = 1;
lg.resize(n + 1, -1);
forto(n + 1, i) {
if (i == 0) continue;
if (i == logpow) {
logpow *= 2;
logval++;
}
lg[i] = logval;
}
forto(19, i) {
if (i == 0) pow2.push_back(1);
else pow2.push_back(pow2.back() * 2);
}
}
int query(int l, int r) {
int sz = r - l + 1;
int j = lg[sz];
int thepower = pow2[j];
int leftmax = sparse[l][j];
int rightmax = sparse[r - thepower + 1][j];
return max(leftmax, rightmax);
}
int minimum_jumps(int a, int b, int c, int d) {
if (query(c, d) < arr[b]) return -1;
int ll = c;
int rr = d;
while (rr - ll >= 1) {
int middle = (ll + rr) / 2;
if (query(c, middle) < arr[b]) ll = middle + 1;
else rr = middle;
}
c = ll;
if (rpts[c].second >= b) return -1;
int l = max(lpts[c].second + 1, a);
int r = b;
int maximum = query(l, r);
int S = ind[maximum];
int T = c;
int sheight = arr[S];
int theight = arr[T];
int steps = 0;
int power = 1 << 18;
int blift = 18;
int index = S;
while (blift >= 0) {
auto dest = greedylift[index][blift];
if (dest.first <= theight && dest.second != -1) {
steps += power;
index = dest.second;
}
blift--;
power /= 2;
}
power = 1 << 18;
blift = 18;
while (blift >= 0) {
auto dest = rightlift[index][blift];
if (dest.first <= theight && dest.second != -1) {
steps += power;
index = dest.second;
}
blift--;
power /= 2;
}
if (arr[index] == theight) return steps;
else return -1;
}
