#include "jumps.h" #include<bits/stdc++.h> using namespace std; template<class T>void maximize(T& a, T b){ if(a < b){ a = b; } } const int lim = 2e5 + 5; const int INF = 2e9; int n, h[lim], L[lim][18], R[lim][18], best[lim][18]; bool is_sub1 = true; void init(int __n, vector<int>__h){ n = __n + 2; __h.insert(__h.begin(), INF); __h.push_back(INF); stack<int>st; for(int i = 0; i < n; st.push(i++)){ if((h[i] = __h[i]) != i && h[i] != INF){ is_sub1 = false; } while(!st.empty() && h[st.top()] < h[i]){ st.pop(); } L[i][0] = (st.empty() ? i : 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(); } best[i][0] = (h[L[i][0]] > h[R[i][0] = (st.empty() ? i : st.top())] ? L[i][0] : R[i][0]); } for(int j = 1; j < 18; j++){ for(int i = 0; i < n; i++){ L[i][j] = L[L[i][j - 1]][j - 1]; R[i][j] = R[R[i][j - 1]][j - 1]; best[i][j] = best[best[i][j - 1]][j - 1]; } } } int minimum_jumps(int A, int B, int C, int D){ A++; B++; C++; D++; if(is_sub1){ return C - B; } if(A == B && C == D){ int ans = 0; for(int i = 17; i > -1; i--){ if(h[best[A][i]] <= h[C]){ A = best[A][i]; ans |= 1 << i; } } for(int i = 17; i > -1; i--){ if(h[R[A][i]] <= h[C]){ A = R[A][i]; ans += 1 << i; } } return A == C ? ans : -1; } if(C == D){ maximize(A, L[C][0] + 1); if(A > B){ return -1; } for(int i = 17; i > -1; i--){ if(R[A][i] <= B){ A = R[A][i]; } } int ans = 0; for(int i = 17; i > -1; i--){ if(h[best[A][i]] <= h[C]){ A = best[A][i]; ans |= 1 << i; } } for(int i = 17; i > -1; i--){ if(h[R[A][i]] <= h[C]){ A = R[A][i]; ans += 1 << i; } } return ans; } if(B == C - 1){ return R[B][0] <= D ? 1 : -1; } int p = B + 1, ans = 0; for(int i = 17; i > -1; i--){ if(R[p][i] < C){ p = R[p][i]; } } if(h[B] > h[p]){ return R[B][0] <= D ? 1 : -1; } for(int i = 17; i > -1; i--){ if(L[B][i] >= A && h[L[B][i]] < h[p]){ B = L[B][i]; } } if(L[B][0] >= A){ if(R[L[B][0]][0] <= D){ return 1; } } else{ for(int i = 17; i > -1; i--){ if(h[best[B][i]] <= h[p]){ ans |= 1 << i; B = best[B][i]; } } if(B == p){ return R[p][0] <= D ? ans + 1 : -1; } if(L[B][0] != 0 && R[L[B][0]][0] <= D){ return ans + 2; } } for(int i = 17; i > -1; i--){ if(R[B][i] < C){ B = R[B][i]; ans += 1 << i; } } return R[B][0] >= C && R[B][0] <= D ? ans + 1 : -1; }