Subtask 1 [30%]

Brute force each query by looping through each \(l_{i}\) to \(r_{i}\) for the existence of at most one peak.

Time Complexity: \(O(NQ)\)

Subtask 2 [70%]

Returning back to the definition the problem gives us, for each interval \([l, r]\) we want an index \(m\) to exist such that the interval \([l, m]\) is non-decreasing and that the interval \([m, r]\) is non-increasing.

As such, we do some preprocessing. For each index \(i\), record down the furthest left index \(ninc[i]\) and furthest right index \(ndec[i]\) such that the interval \([ninc[i], i]\) is non-increasing and that the interval \([i, ndec[i]]\) is non-decreasing. For each query, if \(ndec[l_{i}] >= ninc[r_{i}]\), then there exists a non-decreasing interval that spans from \(l_{i}\) and that transitions into a non-increasing interval that spans until \(r_{i}\). Calculating \(ninc\) and \(ndec\) values can each be done with a single loop.

Time Complexity: \(O(N + Q)\)