You are given an integer array nums and two integers a and b such that a < b.
An array is called good if it can be split into three contiguous parts, in this order, such that:
a.[a, b] inclusive.b.Any of the three parts may be empty.
In one adjacent swap, you may swap two neighboring elements of nums.
Return the minimum number of adjacent swaps required to make nums good. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,3,2,4,5,6], a = 3, b = 4
Output: 1
Explanation:
nums[1] and nums[2]. The array becomes [1, 2, 3, 4, 5, 6].[1, 2], [3, 4], and [5, 6].Example 2:
Input: nums = [9,7,5,3], a = 4, b = 8
Output: 5
Explanation:
One sequence of optimal swaps is as follows:
nums[2] and nums[3]. The array becomes [9, 7, 3, 5].nums[1] and nums[2]. The array becomes [9, 3, 7, 5].nums[0] and nums[1]. The array becomes [3, 9, 7, 5].nums[1] and nums[2]. The array becomes [3, 7, 9, 5].nums[2] and nums[3]. The array becomes [3, 7, 5, 9].[3], [7, 5], and [9].Example 3:
Input: nums = [3,7,5,9], a = 4, b = 8
Output: 0
Explanation:
The array is already good. No swaps are needed.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= a < b <= 109Replace each element with its group number: 0 if it is less than a, 1 if it is in the range [a, b], and 2 if it is greater than b.
After this replacement, the goal is to make the array sorted in non-decreasing order.
With adjacent swaps, the minimum number of swaps needed is the number of inversions in this group array.
Since there are only three possible group values, scan from left to right and count how many previous values are greater than the current value.
[1,3,2,4,5,6] 3 4
[9,7,5,3] 4 8
[3,7,5,9] 4 8