Trong lớp ITK25, ntnhan_itk25 được mọi người kính nể gọi là thủ khoa. Cậu còn sở hữu một "kỹ năng" đặc biệt: bạn bên cạnh vừa gõ xong một dòng code thì trên màn hình của Thành Nhân đã xuất hiện một dòng giống hệt. Đáng tiếc, code được chép sang đầy đủ bao nhiêu thì ý tưởng lại thất lạc bấy nhiêu.

Ở buổi học trước, ntnhan_itk25 đã chép được một đoạn chương trình và vượt qua các bộ dữ liệu nhỏ. Hôm nay, thầy giáo tăng kích thước dữ liệu khiến chương trình chạy mãi không xong. Người bạn từng viết đoạn code lại vắng mặt, còn ntnhan_itk25 thì không nhớ nổi các biến B, p và t dùng để làm gì.

Đoạn code ntnhan_itk25 đã chép nhận một dãy số nguyên ~A~ gồm ~N~ phần tử và thực hiện như sau:

FOR i <- 1 TO N DO
    B[i] <- A[i]
    p <- i

    WHILE p > 1 DO
        IF B[p - 1] <= B[p] THEN
            BREAK
        END IF

        t <- B[p]
        B[p] <- B[p - 1]
        B[p - 1] <- t
        p <- p - 1
    END WHILE

    PRINT B[i] - B[1]
END FOR

Trong đoạn code trên:

• Các mảng ~A~ và ~B~ được đánh số từ ~1~. Mảng ~B~ được giữ nguyên giữa các vòng lặp.
• <- là phép gán. Các lệnh được thực hiện tuần tự từ trên xuống.
• BREAK kết thúc ngay vòng lặp WHILE gần nhất.
• PRINT x bổ sung giá trị ~x~ vào cuối dãy kết quả.

Không thể tiếp tục chờ người khác chép lời giải cho mình, ntnhan_itk25 đành nhờ bạn xác định dãy số mà đoạn code trên sẽ in ra.

Dữ liệu vào

Vào từ file văn bản COPYCODE1.INP gồm:

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \leq N \leq 2 \cdot 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ (~-10^9 \leq A_i \leq 10^9~).

Dữ liệu ra

Ghi ra file văn bản COPYCODE1.OUT kết quả theo yêu cầu sau:

• In ra một dòng gồm ~N~ số nguyên, theo đúng thứ tự được các lệnh PRINT tạo ra.

Ví dụ 1

Input

6
3 -5 4 -2 -8 7

Output

0 8 9 9 12 15

Giải thích

Ở vòng lặp đầu tiên, đoạn code gán ~B_1 = 3~ và in ra ~B_1 - B_1 = 0~.

Ở vòng lặp thứ hai, sau khi gán ~B_2 = -5~, đoạn code đổi chỗ hai giá trị ~3~ và ~-5~. Khi đó, ~B_1 = -5~, ~B_2 = 3~ và giá trị tiếp theo được in ra là ~8~. Tiếp tục thực hiện đoạn code thu được toàn bộ dãy kết quả như trên.

Ràng buộc

• Subtask 1 (20%): ~N \leq 3000~.
• Subtask 2 (80%): Không có ràng buộc nào thêm.