Sequential Purchase Cost with Running-Minimum Discount

Problem Items are purchased in the given order. The first is bought at full price; each subsequent item gets a discount equal to the LOWEST price among all previously purchased items (floored at 0). Compute the total cost.

Input / Output

• Input: int array prices (purchase order fixed).
• Output: total amount paid.

Constraints

• n up to 10^6 — O(n) single pass; no re-sorting (order is fixed by the problem).

Example

• prices = [5, 3, 4, 2]: 5 + max(3−5,0)=0 + max(4−3,0)=1 + max(2−3,0)=0 → total 6. Note the discount is the min of listed PRICES, not of amounts paid.