You are given an integer array nums.
A subarray of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j].
You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri].
Return an integer array ans of length q, where ans[i] is the answer to the ith query.
Note:
Example 1:
Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]
Output: [2,3,4]
Explanation:
queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
[3] and [1]. The total number of stable subarrays is 2.queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
[1], [2], and [1, 2]. The total number of stable subarrays is 3.queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
[3], [1], [2], and [1, 2]. The total number of stable subarrays is 4.Thus, ans = [2, 3, 4].
Example 2:
Input: nums = [2,2], queries = [[0,1],[0,0]]
Output: [3,1]
Explanation:
queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
[2], [2], and [2, 2]. The total number of stable subarrays is 3.queries[1] = [0, 0], the subarray is [nums[0]] = [2].
[2]. The total number of stable subarrays is 1.Thus, ans = [3, 1].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i] = [li, ri]0 <= li <= ri <= nums.length - 1