Company: Myntra_20sep
Difficulty: medium
Perfect Subarrays Problem Description An array is called perfect if it can be sorted in ascending order by selecting any element from the array and adding a negative sign in front of it. This operation can be performed any number of times. For example: [3,1,2,4] can be turned sorted if we add a negative sign in front of 3, i.e., [-3,1,2,4] . You will be given an array seq of n integers with distinct entries ranging from [1, n] (inclusive). You have to find the number of subarrays in seq that are perfect. Input Format Input: First line of input contains integer n representing the number of elements in the array. Second line of input contains a list of n space separated integers, seq , representing the array. Output Format Output: Output an integer representing the number of subarrays in seq that are perfect. Examples Example 1: Input: 3 2 3 1 Output: 5 Explanation: Consider the array seq = [2, 3, 1] . Contiguous Subarrays: Subarray: [2] The single-element subarray is already sorted. Per