Auction Lot Markdown Cascade

An auction house lines up n lots for a single sale, displayed in the exact order buyers will see them, each carrying a listed price. As a closing-day promotion, every lot's price is discounted by the price of the nearest lot appearing later in the line whose price is no higher than its own. A lot that has no such later lot -- because every lot after it costs strictly more, or it is the last lot in the line -- keeps its full listed price. Determine the final price of every lot once this single discount rule has been applied.

Input format

• Line 1: an integer n, the number of lots.
• Line 2: n space-separated integers price_1, ..., price_n, the listed price of each lot in the order they are displayed.

Output format

Print n space-separated integers: the final price of each lot, in the same order, after its discount (if any) has been applied.

Constraints

• 1 <= n <= 500
• 1 <= price_i <= 1000

7
8 4 6 2 3 8 4

4 2 4 2 3 4 4

5
1 2 3 4 5

1 2 3 4 5