Shared code

#include <bits/stdc++.h>
using namespace std;

#define repeat(i,n) for(int i = 0 ; i < n ; i++)
#define repeat_range(i,a,n) for(int i = a ; i < n ; i++)
#define PB push_back
#define F first
#define S second
#define max_ll(a,b) ((a) > (b) ? (a) : (b))
#define min_ll(a,b) ((a) < (b) ? (a) : (b))

typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9 ; 
const int MOD = 1e9+7;

int main() {
    int n , q ; 
    cin >> n >> q; 
    vector<int> arr(n) ; 
    repeat(i,n)
        cin >> arr[i];

    vector<int> ngg(n) ; 

    stack<pair<int,int>> s ; 
    ngg[n-1] = INF ; 
    s.push({arr[n-1],n-1}) ; 
    for(int i = n-2 ; i>=0 ; i--){
        while(!s.empty () && s.top().first <= arr[i])
            s.pop() ; 
        if(!s.empty())
            ngg[i] = s.top().second ; 
        else 
            ngg[i] = INF ; 
        s.push({arr[i],i}) ; 
    }
    
    // Binary - lifting 
    int k = 32 ;
    vector<vector<int>> dp(k+1,vector<int>(n)) ;

    for(int i = 0 ; i<n ; i++)
        dp[0][i] = ngg[i] ; 

    for(int i = 1 ; i<=k ; i++)
        for(int j = 0 ; j<n ; j++){
            if(dp[i-1][j] == INF)
                dp[i][j] = INF ; 
            else
                dp[i][j] = dp[i-1][dp[i-1][j]] ; // 4 1 2 2 3
        }

    repeat(i,q){
        int a , b ; cin >> a >> b ; a-- ; b-- ; 
        int s = 0 , e = b-a+1 , ans = 1 ; // Possible value of the answer
        while(s<=e){
            int m = (s+e)/2 , idx = a , curr = 1 ;
            for(int i = 0 ; (1<<i) <= m ; i++){
                if((1<<i)&m){
                    idx = dp[i][idx];
                    if(idx == INF || idx > b)
                        break ; 
                    else 
                        curr += (1<<i) ; 
                }
            }
            if(curr < m)
                e = m-1 ; 
            else{
                s = m+1 ; 
                ans = max(ans,curr) ;
            }
        }
        cout << ans << endl ; 
    }

    return 0;
}