Subarray Removal

Problem Overview

• Count the subarrays whose removal leaves a non-empty array that is sorted in increasing order.
• Input: an array of n integers; Output: the number of valid contiguous subarrays to remove.
• Subarray means any contiguous segment; the remaining array after removal must not be empty.
• Real-world context: removing a faulty segment to restore ordered data or sequences.
• From Deshaw interviews; a classic coding interview problem and interview question.