CTDL - set4 - Giá trị nhỏ nhì trong set

Cho một dãy \(N\) số nguyên dương \(a_1, a_2, ... , a_N.\)

Yêu cầu

Với mỗi \(i(2 \le i \le N)\), hãy in ra giá trị nhỏ thứ 2 trong đoạn \(1 → i\) trên dãy \(a\).

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((1 \le N \le 10^5)\) − Kích thước của dãy.
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, ... , a_N\) \((−10^9 \le a_i \le 10^9)\) \((a_1 \ne a_2)\).

Output

In ra trên \(N − 1\) dòng, dòng thứ \(i\) \((2 \le i \le N)\) là giá trị nhỏ thứ 2 trong đoạn \(1 → i\).

Ví dụ

5 
 1 5 3 2 1

5 
 3 
 2 
 2

5
 4 3 2 2 2

4 
 3 
 3 
 3