Compute final prices with next smaller discount

You are given an integer array prices of length n, where prices[i] is the original price of the i-th item.

For each item i, find the first index j > i such that prices[j] <= prices[i]. That prices[j] becomes the discount for item i, so the final price of item i is:

• prices[i] - prices[j] if such j exists
• otherwise prices[i]

Return an array finalPrices of length n containing the final price for each item.

Input

• prices: array of integers

Output

• finalPrices: array of integers

Example

• Input: prices = [8, 4, 6, 2, 3]
• Output: [4, 2, 4, 2, 3]

Constraints (typical)

• 1 <= n <= 2e5
• 1 <= prices[i] <= 1e9