Alternative Approach

A key observation is that a subarray [l,r] is valid when max(l,r) - min(l,r) = r - l. This problem appears challenging to maintain efficiently, leading us to consider block decomposition techniques (given the constraints of 1.2e5 elements and 7-second time limit).

Let's divide the array into blocks of size S. We'll handle three cases: left partial blocks (L), right partial blocks (R), and complete middle blocks (M). The solution involves six contribution types: LL, LM, LR, MM, MR, RR, plus special cases where queries fall entirely within a single block.

// Block preprocessing example
void preprocessBlocks() {
    for(int block = 1; block <= total_blocks; block++) {
        int start = block_size * (block-1) + 1;
        int end = min(n, block_size * block);
        
        // Calculate valid subarrays within the block
        for(int i = start; i <= end; i++) {
            for(int j = i; j <= end; j++) {
                if(range_max(i,j) - range_min(i,j) == j - i) {
                    block_data[block][i-start+1][j-start+1] = 1;
                }
            }
        }
        
        // Compute prefix sums for efficient querying
        for(int i = 1; i <= block_size; i++) {
            for(int j = 1; j <= block_size; j++) {
                block_data[block][i][j] += block_data[block][i-1][j] 
                                         + block_data[block][i][j-1] 
                                         - block_data[block][i-1][j-1];
            }
        }
    }
}

The complexity is O(nS + n²/S + qS), where S is optimally set around 1.618√n. This approach requires careful implementation to handle memory constraints and optimize performance.

Optimal Solution

The standard solution uses an offline approach with a sweep line algorithm. We process queries by increasing right andpoints while maintaining answers for all left endpoints.

Key components:

1. Maintain max and min values using monotonic stacks
2. Track the expression (max-min) - (r-l) wich is always ≥ 0
3. Use a segment tree to count zero occurrences efficiently

// Segment tree implementation for counting valid subarrays
struct SegmentTree {
    struct Node {
        int current_min, min_count;
        int historical_min, historical_count;
        int lazy_add, historical_lazy;
    } tree[N*4];
    
    void push(int node) {
        // Propagate lazy updates to children
        // Maintain historical minimum information
    }
    
    void update(int l, int r, int val, int node=1, int node_l=1, int node_r=n) {
        // Apply range updates and maintain statistics
    }
    
    int query(int l, int r, int node=1, int node_l=1, int node_r=n) {
        // Query historical zero counts in range [l,r]
    }
};

The solution achieves O(n log n) complexity by leveraging the segment tree's ability to track historical minimum values and their occurrence counts.