#include "jumps.h" #include<bits/stdc++.h> using namespace std; const int lim = 2e5 + 5; int n, h[lim], L[lim], R[lim], up[lim][18]; bool is_sub1 = true; void init(int __n, vector<int>__h){ n = __n; stack<int>st; for(int i = 0; i < n; st.push(i++)){ if((h[i] = __h[i]) != i + 1){ is_sub1 = false; } while(!st.empty() && h[st.top()] <= h[i]){ st.pop(); } L[i] = (st.empty() ? -1 : st.top()); } while(!st.empty()){ st.pop(); } for(int i = n - 1; i > -1; st.push(i--)){ while(!st.empty() && h[st.top()] <= h[i]){ st.pop(); } R[i] = (st.empty() ? -1 : st.top()); if(L[i] != -1 || R[i] != -1){ up[i][0] = (R[i] == -1 || (L[i] != -1 && h[L[i]] > h[R[i]]) ? L[i] : R[i]); } else{ up[i][0] = i; } } for(int j = 1; j < 18; j++){ for(int i = 0; i < n; i++){ up[i][j] = up[up[i][j - 1]][j - 1]; } } } int minimum_jumps(int A, int B, int C, int D){ if(is_sub1){ return C - B; } if(n <= 2000){ queue<int>q; vector<int>f(n, -1); for(int i = A; i <= B; i++){ q.push(i); f[i] = 0; } while(!q.empty()){ int u = q.front(); q.pop(); if(C <= u && D >= u){ return f[u]; } if(L[u] != -1 && f[L[u]] == -1){ f[L[u]] = f[u] + 1; q.push(L[u]); } if(R[u] != -1 && f[R[u]] == -1){ f[R[u]] = f[u] + 1; q.push(R[u]); } } } else if(A == B && C == D){ if(h[A] < h[C]){ int ans = 0; for(int i = 17; i > -1; i--){ if(h[up[A][i]] < h[C]){ A = up[A][i]; ans |= 1 << i; } } return ans + 1; } } return -1; }