AT_abc476_c [ABC476C] Third Largest Number

$ 3 $ 以上の整数 $ N $ と長さ $ N $ の正整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ k=3,4,\ldots,N $ それぞれに対し以下の問題を解いてください： - $ A_1,A_2,\ldots,A_k $ を降順に並べたとき、前から $ 3 $ 番目にくる値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ N-2 $ 行出力せよ。 $ i $ 行目 $ (1\le i\le N-2) $ には $ k=i+2 $ とした時の答えを出力せよ。

### Sample Explanation 1 - $ k=3 $ のとき： $ A_1,A_2,A_3 $ を降順に並べると $ 2,1,1 $ となります。前から $ 3 $ 番目に来る値は $ 1 $ なので、 $ 1 $ 行目には $ 1 $ を出力してください。 - $ k=4 $ のとき： $ A_1,A_2,A_3,A_4 $ を降順に並べると $ 2,2,1,1 $ となります。前から $ 3 $ 番目に来る値は $ 1 $ なので、 $ 2 $ 行目には $ 1 $ を出力してください。 - $ k=5 $ のとき： $ A_1,A_2,A_3,A_4,A_5 $ を降順に並べると $ 3,2,2,1,1 $ となります。前から $ 3 $ 番目に来る値は $ 2 $ なので、 $ 3 $ 行目には $ 2 $ を出力してください。 ### Constraints - $ 3\le N\le 5\times 10^5 $ - $ 1\le A_i\le 10^9 $ - 入力される値は全て整数