Với mỗi phần tử A[i], cần tìm xem có bao nhiêu đoạn liên tiếp mà A[i] là lớn nhất. Việc này ta sẽ sử dụng Stack để làm.

• Với A[i] tìm j gần nhất sao cho j < i và A[j] >= A[i] (chú ý trường hợp A[i] = A[j] nên mới có A[j] >= A[i])
• Với A[i] tìm k gần nhất sao cho i < k vào A[k] > A[i]

=> số đoạn mà A[i] lớn nhất là (i-j)*(k-i) lưu vào mảng SL[i]

Sắp xếp lại mảng A tăng dần sau đó tính cộng dồn T[i] = T[i-1] + SL[i].

Với mỗi truy vấn L,R :

• Tìm vị trí x, và y trên dãy A sao cho A[x] nhỏ nhất và A[y] lớn nhất mà vẫn thuộc đoạn [L,R] => kq += T[y] – T[x-1].