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 ≤ i ≤ 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 ≤ N ≤ 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 ≤ a_i ≤ 10^9)\) \((a_1 \ne a_2)\).

Output

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

Ví dụ