FastPrepFastPrep
Problem Brief

Subarray Removal

OA

Given an array arr of n integers, find the number of its subarrays such that removing the subarray creates a non-empty array that is sorted in increasing order.

Note: A subarray is defined as any contiguous segment of the array.

1Example 1

Input
arr = [1, 2, 1, 2]
Output
7
Explanation
Example 1 illustration

There are 7 subarrays that on removal produce a non-empty sorted array. Hence, the answer is 7.

The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.

2Example 2

Input
arr = [3, 1, 2]
Output
3
Explanation

The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.

3Example 3

Input
arr = [1, 2, 2, 6, 1, 3]
Output
10
Explanation

The subarrays [1, 2, 2, 6], [1, 2, 2, 6, 1], [2, 2, 6], [2, 2, 6, 1], [2, 6], [2, 6, 1], [6], [6, 1], [1, 3] and [1] give a non-empty sorted array on removal.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 2×10^5
  • 1 ≤ arr[i] ≤ 10^9
public long getNumSubarrays(int[] arr) {
  // write your code here
}
Input

arr

[1, 2, 1, 2]

Output

7

Sign in to submit your solution.