nqson đang xếp hàng mua gấu bông OZ Genshin Impact phiên bản giới hạn. Để gióng hàng cho thẳng, nqson cần phải lấy người đứng trước che gáy một người khác đứng trước người đó. Ví dụ: nqson - lvminh - tmtien thì nqson lấy lvminh che gáy tmtien.

Nhưng do nqson quá cao nên anh ấy cần phải gióng hàng bằng người cao hơn mình. nqson muốn biết mỗi người trong hàng, ai là người cao hơn đứng trước mình và gần mình thứ 2.

Ví dụ: chiều cao của nqson, lvminh, tmtien lần lượt là 1 3 2 thì tmtien là người cao hơn đứng trước nqson và gần nqson thứ 2

Đầu vào

Dòng đầu tiên chứa một số tự nhiên \(n\).

Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,a_3,...,a_n\) là chiều cao của từng người trong hàng ( \(a_2\) đứng trước \(a_1\) ).

Đầu ra

In ra dãy số \(x_1,x_2,x_3,...,x_n\) với \(x_i\) là độ cao của người cao hơn đứng trước gần người i thứ 2 ( Nếu không có, xuất ra -1 )

Giới hạn

\(1 \le n \le 10^6 ; 1 \le a_i \le 10^{9}\)

Ví dụ 1

Đầu vào:

6
1 1 4 2 5 3

Đầu ra:

2 2 -1 3 -1 -1

Ví dụ 2

Đầu vào:

3
5 5 5

Đầu ra:

-1 -1 -1