Tìm kiếm

Cho mảng \(A\) có \(n\) số nguyên dương \(\{a_1, a_2, \ldots, a_n\}\).

Yêu cầu: Với mỗi số nguyên dương \(a_i\), tìm số nguyên dương \(a_j\) (\(j > i\)) với \(j\) nhỏ nhất thỏa mãn \(a_j\) có nhiều ước hơn \(a_i\); nếu không có số \(a_j\) thỏa mãn thì kết quả tìm kiếm là \(-1\).

Input

Dữ liệu vào:có thông tin sau:

• Dòng đầu tiên là số nguyên dương \(n\) (\(n \le 2 \times 10^5\));

• Dòng thứ hai có \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^9\)).
  Dữ liệu đảm bảo: \(\max\{a_i\} - \min\{a_i\} \le 10^6\) với mọi \(i = 1..n\). Các số trên cùng một dòng trong dữ liệu được viết cách nhau bởi dấu cách trống.

Ràng buộc:

• Subtask 1 (\(20\%\) số điểm): Dữ liệu vào có \(n \le 10^3\) và \(a_i \le 10^4\) với mọi \(i = 1..n\).

• Subtask 2 (\(50\%\) số điểm): Dữ liệu vào có \(n > 10^3\) và \(a_i \le 10^6\) với mọi \(i = 1..n\).

• Subtask 3 (\(30\%\) số điểm): Không có ràng buộc nào thêm.

Output

In ra kết quả một dòng có \(n\) số nguyên theo thứ tự là kết quả tìm kiếm theo yêu cầu. Các số nguyên ghi cách nhau bởi một dấu cách trống.

Example

Input:

6
6 18 7 10 9 8

Output:

18 -1 10 -1 8 -1

Note

Số ước tương ứng của các số là: \(4, 6, 2, 4, 3, 4\). Kết quả tìm kiếm là:

• \(a_1 = 18\) (vì \(6 > 4\));

• \(a_2 = -1\) (vì không có số lớn hơn \(6\));

• \(a_3 = 10\) (vì \(4 > 2\) và \(a_4\) gần nhất);

• \(a_4 = -1\) (vì không có số lớn hơn \(4\));

• \(a_5 = 8\) (vì \(4 > 3\));

• \(a_6 = -1\) (vì không có số bên phải).