Silent Auction Third Distinct Bid

A silent auction records every bid placed on an item as it comes in. Multiple bidders can end up placing the exact same amount, so the recorded list of bids may contain repeats. The auction house wants to announce the third-highest DISTINCT bid amount, to recognize the "bronze tier" bidder. If the recorded bids only produced one or two distinct amounts in total, announce the highest bid amount instead.

Input format

• Line 1: an integer n, the number of recorded bids.
• Line 2: n space-separated integers, the bid amounts in the order they were recorded. Amounts may repeat and may be any 32-bit signed integer (a negative "bid" simply represents a value below the auction's reference point).

Output format

Print a single integer: the third-highest distinct bid amount, or the highest bid amount if fewer than three distinct amounts were recorded.

Constraints

• 1 <= n <= 10^4
• -2^31 <= bid[i] <= 2^31 - 1

3
3 2 1

1

2
1 2

2