Cho một mảng A gồm n số nguyên dương a₁, a₂, …, aₙ.

Ta định nghĩa hai hàm số F(X) và G(X) như sau:

• F(X) bằng giá trị Z nhỏ nhất thỏa mãn X < Z ≤ N và aₓ < a𝓏;
• G(X) bằng giá trị Z nhỏ nhất thỏa mãn X < Z ≤ N và aₓ > a𝓏.

Với mỗi chỉ số i, hãy tính giá trị A[G(F(i))].

Nếu giá trị này không tồn tại thì ghi -1, nếu giá trị trên tồn tại thì ghi A[G(F(i))].

Yêu cầu: Với mỗi chỉ số i (1 ≤ i ≤ N), hãy tính kết quả tương ứng.

INPUT

• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 30000);
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10¹⁸).

OUTPUT

Gồm N số nguyên, số thứ i là A[G(F(i))] nếu giá trị này tồn tại, hoặc -1 nếu không tồn tại.

Ví dụ

Sample Input

8
3 7 1 7 8 4 5 2

Sample Output

1 4 4 4 -1 2 -1 -1

Giải thích

Từ đó, với mỗi vị trí i, ta lấy giá trị của G(F(i)):

1 4 4 4 -1 2 -1 -1