#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
const int MAXLOG = 20;
const int INF = 2e9 + 10;
int n;
int h[MAXN];
int l[MAXN];
int r[MAXN];
int nxt[MAXN];
struct SparseTable
{
int st[MAXN][MAXLOG];
int lg[MAXN];
void build()
{
for(int i = 1; i <= n; i++)
{
st[i][0] = h[i];
}
for(int j = 1; (1 << j) <= n; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
{
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
for(int i = 2; i <= n; i++)
{
lg[i] = lg[i / 2] + 1;
}
}
int query(int left, int right)
{
int len = right - left + 1;
int k = lg[len];
return max(st[left][k], st[right - (1 << k) + 1][k]);
}
};
struct BinaryLifting
{
int lift[MAXN][MAXLOG];
void build(int par[])
{
for(int i = 1; i <= n; i++)
{
lift[i][0] = par[i];
}
for(int j = 1; (1 << j) <= n; j++)
{
for(int i = 1; i <= n; i++)
{
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
}
}
int anc(int i, int j)
{
return lift[i][j];
}
};
SparseTable sparse;
BinaryLifting goL, goR, goLR;
void fill_l()
{
stack < int > st;
st.push(0);
for(int i = 1; i <= n; i++)
{
while(h[st.top()] < h[i])
{
st.pop();
}
l[i] = st.top();
st.push(i);
}
// cout << endl;
// cout << "To the left : " << endl;
// for(int i = 1; i <= n; i++)
// {
// cout << l[i] << " ";
// }
// cout << endl;
}
void fill_r()
{
stack < int > st;
st.push(n + 1);
for(int i = n; i >= 1; i--)
{
while(h[st.top()] < h[i])
{
st.pop();
}
r[i] = st.top();
st.push(i);
}
r[0] = r[n + 1] = n + 1;
// cout << endl;
// cout << "To the right : " << endl;
// for(int i = 1; i <= n; i++)
// {
// cout << r[i] << " ";
// }
// cout << endl;
}
void fill_nxt()
{
for(int i = 1; i <= n; i++)
{
nxt[i] = l[i];
if(h[r[i]] > h[l[i]])
nxt[i] = r[i];
}
// cout << endl;
// cout << "To the max : " << endl;
// for(int i = 1; i <= n; i++)
// {
// cout << nxt[i] << " ";
// }
// cout << endl;
}
void init(int N, vector < int > H)
{
n = N;
for(int i = 1; i <= n; i++)
{
h[i] = H[i - 1];
}
h[0] = INF;
h[n + 1] = INF;
fill_l();
fill_r();
fill_nxt();
sparse.build();
goL.build(l);
goR.build(r);
goLR.build(nxt);
}
int minimum_jumps(int fromL, int fromR, int toL, int toR)
{
fromL++;
fromR++;
toL++;
toR++;
int max_to = sparse.query(toL, toR);
int max_between = sparse.query(fromR, toL - 1);
if(max_between > max_to)
return -1;
int idx = fromR;
for(int j = MAXLOG - 1; j >= 0; j--)
{
if(goL.anc(idx, j) >= fromL && h[goL.anc(idx, j)] <= max_to)
{
idx = goL.anc(idx, j);
}
}
if(goR.anc(idx, 0) >= toL)
return 1;
int steps = 0;
for(int j = MAXLOG - 1; j >= 0; j--)
{
if(h[goLR.anc(idx, j)] <= max_to && r[goLR.anc(idx, j)] < toL)
{
steps += (1 << j);
idx = goLR.anc(idx, j);
}
}
if(h[nxt[idx]] <= max_to)
return steps + 2;
for(int j = MAXLOG - 1; j >= 0; j--)
{
if(r[goR.anc(idx, j)] < toL)
{
steps += (1 << j);
idx = goR.anc(idx, j);
}
}
return steps + 2;
}
// int main()
// {
// int n, q;
// std::vector <int> h;
// std::cin >> n >> q;
// h.resize(n);
// for (int i = 0 ; i < n ; ++i)
// {
// std::cin >> h[i];
// }
// std::vector <std::array <int,4>> queries(q);
// for (int i = 0 ; i < q ; ++i)
// {
// std::cin >> queries[i][0] >> queries[i][1] >> queries[i][2] >> queries[i][3];
// }
// init(n, h);
// for (int i = 0 ; i < q ; ++i)
// {
// std::cout << minimum_jumps(queries[i][0], queries[i][1], queries[i][2], queries[i][3]) << '\n';
// }
// return 0;
// }
/*
7 1
3 2 1 6 4 5 7
4 4 6 6
*/
