Trong cuộc thi Tin học trẻ, mỗi thí sinh phải trả lời \(n\) câu hỏi. Để tăng tính hấp dẫn của cuộc thi, ban tổ chức quyết định đưa ra \(n\) số điểm thưởng \(a_1, a_2, \ldots, a_n\). Theo thể lệ của cuộc thi, thí sinh trả lời đúng \(k\) câu hỏi (\(1 \leq k \leq n\)) sẽ nhận được số điểm thưởng bằng số lớn nhất trong các số \(a_1, a_2, \ldots, a_k\).

Yêu cầu: Xác định số điểm thưởng của thí sinh tương ứng với mỗi giá trị \(k\) từ \(1\) đến \(n\).

Input

• Dòng đầu chứa số nguyên dương \(n\) không vượt quá \(30000\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\), mỗi số không vượt quá \(10^3\).

Output

• Ghi ra một dòng gồm \(n\) số là điểm thưởng cho thí sinh trả lời đúng lần lượt \(1, 2, \ldots, n\) câu hỏi.

Example

3
6 1 7

6 6 7