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 đưa ra \(n\) số điểm thưởng:

Theo thể lệ của cuộc thi, nếu thí sinh trả lời đúng \(k\) câu hỏi \((1 \le k \le n)\) thì sẽ nhận được số điểm thưởng bằng giá trị lớn nhất trong các số:

Yêu cầu

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

Input

• Dữ liệu vào từ tệp BAI2.INP.
• Dòng đầu chứa số nguyên dương \(n\) \((n \le 30000)\).
• Dòng thứ hai chứa \(n\) số nguyên dương:

Trong đó mỗi số không vượt quá \(10^3\).

Output

• Ghi ra tệp BAI2.OUT gồm \(n\) số:
• Số thứ \(i\) là điểm thưởng khi trả lời đúng \(i\) câu hỏi.

Example

3
6 1 7

6 6 7