AT_abc476_c [ABC476C] Third Largest Number

You are given an integer $ N $ not less than $ 3 $ and a length- $ N $ sequence of positive integers $ A=(A_1,A_2,\ldots,A_N) $ . For each $ k=3,4,\ldots,N $ , solve the following problem: - When $ A_1,A_2,\ldots,A_k $ are sorted in descending order, find the third value from the front.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output $ N-2 $ lines. The $ i $ -th line $ (1\le i\le N-2) $ should contain the answer for $ k=i+2 $ .

### Sample Explanation 1 - For $ k=3 $ : sorting $ A_1,A_2,A_3 $ in descending order gives $ 2,1,1 $ . The third value from the front is $ 1 $ , so output $ 1 $ on the first line. - For $ k=4 $ : sorting $ A_1,A_2,A_3,A_4 $ in descending order gives $ 2,2,1,1 $ . The third value from the front is $ 1 $ , so output $ 1 $ on the second line. - For $ k=5 $ : sorting $ A_1,A_2,A_3,A_4,A_5 $ in descending order gives $ 3,2,2,1,1 $ . The third value from the front is $ 2 $ , so output $ 2 $ on the third line. ### Constraints - $ 3\le N\le 5\times 10^5 $ - $ 1\le A_i\le 10^9 $ - All input values are integers.