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.
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:
x, orxwhichever is smaller.
Return the total cost of processing all instructions.
Because the answer can be large, return it modulo .
instructions.1 <= instructions.length <= $10^{5}$1 <= instructions[i] <= $10^{5}$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.
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
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.