The first solution in the editorial can be optimized to \(O(N\log N)\).

Let \(\alpha_L\), \(\alpha_R\) arrays to be the cumulative min array from \(M\) to \(L\) and \(M\) to \(R\) respectively (same as the editorial). Split all pairs with \((l,r)\) with \(L\leq l\leq M\leq r\leq R\) into two types. \((l,r)\) is called first type if \(\alpha_L[l]\leq \alpha_R[r]\), and second type otherwise.

To count the number of good pairs of first type, notice that if \((l,r+1)\) is a good pair of first type, then so is \((l,r)\). So for each \(l\), we can calculate maximum \(r\) such that \((l,r)\) is good and of first type. Let the maximum be \(f(l)\). If we loop from \(M\) to \(L\), then \(f(l)\) is first increasing, then after a point it becomes decreasing (why?), so it can be calculated using two pointers in \(O(R-L)\). Counting good pairs of second type should be similar.