Given an array with length of \(N\).
\(\forall i \in [1, N]\), you have to output the second highest value in the subarray \([1, i]\) (i.e. the second integer after sorting the subarray from higher to lower)
If there are less than two numbers in the subarray, you should print \(0\) instead.
The first line of input contains a number N.
The second line contains N integers.
It is guaranteed that N <= 106 and each number in the array is in the range of [1, 109].
Print one line that contains N numbers, separated by a single white space and end with a newline.