#include "jumps.h" #include<bits/stdc++.h> using namespace std; const int lim = 2e5 + 5; int n, h[lim], L[lim], R[lim]; 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()); } } int minimum_jumps(int A, int B, int C, int D){ if(is_sub1){ return A > D ? -1 : max(0, C - B); } else 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{ } return -1; }