Is This Slice Sorted — Solution & Editorial

Back to the Problem

Prefix-count the DESCENT positions (a_i < a_i−1); a slice is sorted iff it contains none strictly inside.

Complexity: O(N + Q)