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, 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,...,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

Vào từ file văn bản CAU2.INP:

• 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,...,a_n~ mỗi số không vượt quá ~10^3~.

Output

Ghi ra file văn bản CAU2.OUT một dòng gồm ~n~ số là điểm thưởng cho thí sinh trả lời đúng lần lượt là ~1,2,...,n~ câu hỏi.

Example input 1

3
6 1 7

Example output 1

6 6 7

Note 1

• Thí sinh trả lời đúng 1 câu sẽ nhận điểm thưởng là 6;
• Trả lời đúng 2 câu sẽ nhận điểm thưởng là 6;
• Trả lời đúng 3 câu sẽ nhận điểm thưởng là 7.