hardBinary SearchPure DSA~35 min
Total Cost to Insert into a Sorted Buffer
Records arrive one at a time and are inserted into a sorted buffer. The cost of each insertion is the smaller of how many existing records are strictly less than it or strictly greater. Sum the total insertion cost.
Problem
Given an array instructions, insert its elements one by one into an initially empty sorted container. The cost of inserting a value is min(count of elements already inserted that are strictly less than it, count strictly greater than it). Return the total cost modulo 1e9 + 7.
Input
An integer array instructions.
Output
An integer: the total insertion cost modulo 1e9 + 7.
Constraints
- 1 <= instructions.length <= 100000
- 1 <= instructions[i] <= 100000
Examples
Example 1
Input
instructions = [1,5,6,2]
Output
1
Costs are 0,0,0,1 (for 2, one element 1 is smaller) totaling 1.
Example 2
Input
instructions = [1,2,3,6,5,4]
Output
3
The accumulated minimum-side costs total 3.