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òng đầu tiên là số nguyên dương \(n\) \((n \le 2 \cdot 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 \(i = 1..n\).
• Các số trên cùng một dòng trong file dữ liệu được viết cách nhau bởi dấu cách trống.

Output

• Ghi ra 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

6
6 18 7 10 9 8

18 -1 10 -1 8 -1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Dữ liệu vào có \(n \le 10^3\) và \(a_i \le 10^4\) vớ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 \(i = 1..n\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc nào thêm.