Tìm kiếm

Trong một kho dữ liệu, bạn được cho một mảng \(A\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).
Với mỗi vị trí \(i\), hệ thống muốn tìm phần tử gần nhất ở bên phải có số lượng ước dương lớn hơn số lượng ước dương của \(a_i\).

Cụ thể, với mỗi \(i\), hãy tìm chỉ số nhỏ nhất \(j\) sao cho \(j>i\) và số ước dương của \(a_j\) lớn hơn số ước dương của \(a_i\).
Nếu không tồn tại \(j\) như vậy thì kết quả tại vị trí \(i\) là \(-1\).

Bạn cần in ra \(n\) số theo thứ tự là kết quả tương ứng với từng \(i\).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Output

In ra một dòng gồm \(n\) số nguyên, số thứ \(i\) là:

• \(a_j\) với \(j>i\) nhỏ nhất sao cho \(d(a_j) > d(a_i)\) (trong đó \(d(x)\) là số ước dương của \(x\)), hoặc
• \(-1\) nếu không tồn tại.

Giới hạn

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• \(\max(a_i) - \min(a_i) \le 10^6\)

Scoring

• Subtask 1 (20%): \(n \le 10^3\), \(a_i \le 10^4\).
• Subtask 2 (50%): \(n > 10^3\), \(a_i \le 10^6\).
• Subtask 3 (30%): Không có ràng buộc gì thêm.

Input

6
6 18 7 10 9 8

Output

18 -1 10 -1 8 -1