#ifndef davele #include "jumps.h" #endif // davele #include <bits/stdc++.h> #include <vector> #define MASK(i) (1ll<<(i)) using namespace std; const int lim = 2e5, limit = lim+5, mxlog = 20, inf = 2e9; void init(int _N, std::vector<int> H); int minimum_jumps(int a, int b, int c, int d); struct Jury{ int n, q; vector <int> H; int A[limit], B[limit], C[limit], D[limit]; void load (){ cin>>n>>q; H.clear(); for (int i=1; i<=n; i++){ int v; cin>>v; H.push_back(v); } for (int i=1; i<=q; i++) cin>>A[i]>>B[i]>>C[i]>>D[i]; } void process(){ init(n, H); for (int i=1; i<=q; i++) cout<<minimum_jumps(A[i], B[i], C[i], D[i])<<"\n"; } } jury; int L[limit][22], R[limit][22], higher[limit][22], A[limit]; int n; int pos_max (int l, int r){ for (int i=mxlog; i>=0; i--){ if (R[l][i]<=r){ // cerr<<l<<"\n"; l = R[l][i]; } } return l; } void prep(){ stack <int> st; for (int i=0 ; i<n; i++){ while (!st.empty() && A[i]>=A[st.top()]) st.pop(); L[i][0] = st.empty() ? i: st.top(); st.push(i); } // cerr<"ok\n"; while (!st.empty()) st.pop(); for (int i=n-1; i>=0; i--){ while (!st.empty() && A[i]>=A[st.top()]) st.pop(); R[i][0] = st.empty() ? i : st.top(); st.push(i); } for (int i=0; i<n; i++){ higher[i][0] = L[i][0]; if (A[R[i][0]]>A[L[i][0]]) higher[i][0] = R[i][0]; } // cout<<"A:\n"; // for (int i=0; i<n; i++){ // cout<<A[i]<<" "; // } // cout<<"\n"; // cout<<"L:\n"; // for (int i=0; i<n; i++){ // cout<<L[i][0]<<" "; // } // cout<<"\n"; // cout<<"R:\n"; // for (int i=0; i<n; i++){ // cout<<R[i][0]<<" "; // } // cout<<"\n"; // cout<<"high:\n"; // for (int i=0; i<n; i++){ // cout<<higher[i][0]<<" "; // } // cout<<"\n"; for (int i=1; i<=mxlog; i++){ for (int j=0; j<n; j++){ L[j][i] = L[L[j][i-1]][i-1]; R[j][i] = R[R[j][i-1]][i-1]; higher[j][i] = higher[higher[j][i-1]][i-1]; } } } void init(int _N, std::vector<int> H) { A[0] = inf; n = _N; for (int i=1; i<=n; i++){ A[i] = H[i-1]; } A[n+1] = inf; n+=2; // cerr<<"ok\n"; prep(); } int minimum_jumps(int a, int b, int c, int d) { // danh so tu 0 -> danh so tu 1 a++; b++; c++; d++; // cout<<A[a]<<" "<<A[c]<<"\n"; if (b+1==c){ if (R[b][0]<=d) return 1; return -1; } // cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n"; int bestmid = pos_max (b+1, c-1); if (A[b]>A[bestmid]){ return R[b][0] <= d ? 1 : -1; } // cout<<bestmid<<"\n"; int s = b; for (int i=mxlog; i>=0; i--){ if (L[s][i]>=a && A[L[s][i]]<A[bestmid]){ s = L[s][i]; } } // cout<<s<<" "<<"\n"; int ans = 0; if (L[s][0]>=a){ // co the nhay 1 phat an luon if (R[L[s][0]][0]<=d) return 1; } else{ // luu y la co else o day // cout<<s<<"\n"; // nhay theo cac thang higher for (int i=mxlog; i>=0; i--){ if (A[higher[s][i]]<=A[bestmid]){ ans+=MASK(i); s = higher[s][i]; } } // cout<<A[s]<<" "<<s<<"\n"; if (s==bestmid){ return (R[s][0]<=d) ? ans+1 : -1; } if (0<L[s][0] && R[L[s][0]][0]<=d) return ans+2; } for (int i=mxlog; i>=0; i--){ if (R[s][i]<c){ ans+=MASK(i); s = R[s][i]; } } if (R[s][0]<=d && R[s][0]>=c) return ans+1; return -1; } #ifdef davele signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // const string name = "jumps"; if (fopen((name+".inp").c_str(), "r")){ freopen ((name+".inp").c_str(), "r", stdin); freopen ((name+".out").c_str(), "w", stdout); } jury.load(); jury.process(); } #endif // davele