Bài 5: Tìm kiếm

Cho mảng A có n số nguyên dương (a₁, a₂, ..., 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 với j > i và 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 nào thỏa mãn thì kết quả tìm kiếm là -1.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương n ( n <= 2 x 10⁵ );
• Dòng thứ hai có n số nguyên dương a₁, a₂, ..., a_n ( a_i <= 10⁹ ).
• Dữ liệu đảm bảo: max(a_i) - min(a_i) <= 10⁶ 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.

Kết quả ra

Ghi ra file 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.

Ví dụ

Sample Input

6
6 18 7 10 9 8

Sample Output

18 -1 10 -1 8 -1

Giải thích

Số ước tương ứng của các số là: 4 6 2 4 3 4

Kết quả tìm kiếm:
- a₁ = 18 (vì 6 > 4)
- a₂ = -1 (vì không có số nào lớn hơn 6)
- a₃ = 10 (vì 4 > 2 và a₄ gần nhất)
- a₄ = -1 (vì không có số nào có lớn hơn 4)
- a₅ = 8 (vì 4 > 3)
- a₆ = -1 (vì không có số nào bên phải)

Chấm điểm

• Subtask 1 (20% số điểm): n <= 10³ và a_i <= 10⁴ với i = 1..n.
• Subtask 2 (50% số điểm): n <= 10³ và a_i <= 10⁶ với i = 1..n.
• Subtask 3 (30% số điểm): Không có ràng buộc nào thêm.