We’re preparing your current view and syncing the latest data.
You are given an integer array instructions. You start with an empty container and you need to insert all the elements of instructions into the container. The cost of inserting an element is the minimum between the number of elements already in the container that are strictly less than the element you are inserting and the number of elements that are strictly greater than it. Return the total cost to insert all elements from instructions into the container. Since the answer can be large, return it modulo 10^9 + 7.
An array of integers instructions.
An integer representing the total insertion cost modulo 10^9 + 7.
1 <= instructions.length <= 10^5, 1 <= instructions[i] <= 10^5
Example 1
Input
[1,5,6,2]
Output
1
Explanation
Insert 1: cost = 0 (empty), Insert 5: cost = 1 (one element less than 5), Insert 6: cost = 2, Insert 2: cost = min(1,2) = 1, total cost = 0 + 1 + 2 + 1 = 4 modulo 10^9+7 = 4.
Example 2
Input
[1,3,3,3,2,4,2,1,2]
Output
4
Explanation
After all insertions, total cost calculated according to the problem's cost calculation rules is 4.