For the subarray to be sorted starting from the -th integer to the -th integer, for all such that , the condition should be satisfied.
This condition can be checked by simply checking all adjacent elements. That is, if we set as True
or False
based on whether is true, for the subarray to be ascending starting from the -th integer to the -th integer, must all be true.
There are multiple ways to count such pairs.
True
block. For any possible combination of starting and ending points within the block, the condition is satisfied. If the length of the block is , there are combinations.The answer is the sum of for each continuous block of length in . All calculations can be performed in time.