Build a sorted array by inserting numbers one by one and compute the total insertion cost, where each insertion costs the smaller of the counts of existing smaller and greater elements.
Problem
You are given an array instructions where each value is inserted into an initially empty array one at a time.
For each value x = instructions[i], insert it into the current array so that the array remains sorted in non-decreasing order. The cost of this insertion is:
- the number of existing elements strictly less than
x, or - the number of existing elements strictly greater than
x
whichever is smaller.
Return the total cost of processing all instructions.
Because the answer can be large, return it modulo .
Notes
- Equal values are allowed.
- The array is considered sorted after every insertion.
- You only need the total cost, not the final array itself.
Input Format
- A single integer array
instructions. - Each element represents the next value to insert into the sorted array.
Output Format
- Return one integer: the total insertion cost modulo .
Constraints
1 <= instructions.length <= $10^{5}$1 <= instructions[i] <= $10^{5}$- Answer should be computed modulo .
Example 1
Input
instructions = [1,5,6,2]
Output
1
Explanation
Insert 1: cost 0. Insert 5: smaller=1, greater=0, cost 0. Insert 6: smaller=2, greater=0, cost 0. Insert 2: smaller=1, greater=2, cost 1. Total = 1.
Example 2
Input
instructions = [1,2,3,6,5,4]
Output
3
Explanation
The insertion costs are 0, 0, 0, 0, 1, 2 respectively, for a total of 3.
Show 1 more example
Example 3
Input
instructions = [1,3,3,3,2,4,2,1,2]
Output
4
Explanation
Track the number of smaller and greater existing elements at each insertion and sum the smaller count each time.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.