#include <bits/stdc++.h> using namespace std; int n; vector<int> height, dist; vector<vector<int>> adj; void init(int N, vector<int> H) { n = N; height = H; adj.resize(N); stack<int> left, right; for(int i = 0; i < N; i++) { while(!left.empty() && H[left.top()] < H[i]) left.pop(); if(!left.empty()) adj[i].push_back(left.top()); left.push(i); } for(int i = N-1; i >= 0; i--) { while(!right.empty() && H[right.top()] < H[i]) right.pop(); if(!right.empty()) adj[i].push_back(right.top()); right.push(i); } } int minimum_jumps(int A, int B, int C, int D) { queue<int> q; dist.assign(n, INT_MAX); for(int i = A; i <= B; i++) { q.push(i); dist[i] = 0; } while(!q.empty()) { int u = q.front(); q.pop(); if(u >= C && u <= D) continue; for(int i = 0; i < adj[u].size(); i++) { if(dist[adj[u][i]] > dist[u]+1) { q.push(adj[u][i]); dist[adj[u][i]] = dist[u]+1; } } } int ans = INT_MAX; for(int i = C; i <= D; i++) ans = min(ans, dist[i]); if(ans == INT_MAX) return -1; return ans; } // int main() { // int N, Q; // scanf("%d %d", &N, &Q); // vector<int> H(N); // for(int i = 0; i < N; i++) // scanf("%d", &H[i]); // init(N, H); // while(Q--) { // int A, B, C, D; // scanf("%d %d %d %d", &A, &B, &C, &D); // printf("%d\n", minimum_jumps(A, B, C, D)); // } // return 0; // }