Khi đọc đề bài này, chúng tôi khuyên bạn hãy tạm quên rằng mùa hè có 92 ngày và một ngày có 1440 phút. Đây là Berland, và mọi thứ ở đây đều khác.

Monocarp là một sinh viên của một trường đại học tỉnh lẻ tại Berland. Kỳ nghỉ hè vừa mới bắt đầu và sẽ kéo dài trong \(n\) ngày tới. Monocarp từ lâu đã mơ ước được đến thủ đô của Berland, vì vậy cậu ấy sẽ chọn một ngày \(i\) trong số những ngày này để đến thủ đô và ở đó cho đến hết kỳ nghỉ.

Thủ đô của Berland không phải là một thành phố rẻ đỏ, trong khi Monocarp chỉ mang theo 0 Berland dollar. Rõ ràng, số tiền này không đủ để tham quan các địa điểm thú vị hay mua quà lưu niệm. Vì vậy, trong một số ngày ở thủ đô, Monocarp sẽ làm việc tự do (freelancer). Cậu ấy không muốn làm việc ở quê nhà vì đã dành cả năm học để làm bài tập đại học rồi.

Cụ thể, vào ngày thứ \(i\) của kỳ nghỉ, Monocarp có \(a_i\) phút rảnh. Trong ngày đó, cậu sẽ hoặc dùng toàn bộ thời gian để làm việc hoặc để nghỉ ngơi và mua quà lưu niệm.

• Nếu vào đầu ngày thứ \(i\), Monocarp có ít nhất \(a_i\) dollar, thì trong ngày hôm đó cậu sẽ dành thời gian để nghỉ ngơi và mua quà lưu niệm, tiêu tiền với tốc độ 1 dollar mỗi phút. Nói cách khác, cậu sẽ chi tiêu đúng \(a_i\) dollar trong ngày đó.
• Ngược lại, nếu Monocarp có ít hơn \(a_i\) dollar vào đầu ngày, thì cậu sẽ dành cả ngày để làm việc, kiếm được 1 dollar mỗi phút. Tức là cậu sẽ kiếm được đúng \(a_i\) dollar trong ngày đó.

Lưu ý rằng Monocarp luôn đưa ra quyết định cho cả ngày; cậu không thể vừa kiếm tiền vừa tiêu tiền trong cùng một ngày.

Nhiệm vụ của bạn là xác định, với mỗi số ngày \(k\) từ \(1\) đến \(n\), Monocarp sẽ còn lại bao nhiêu dollar sau ngày cuối cùng của kỳ nghỉ nếu cậu chỉ sống ở thủ đô trong đúng \(k\) ngày cuối cùng của kỳ nghỉ (tức là cậu đến thủ đô vào ngày \((n-k+1)\)).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \le n \le 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((1 \le a_i \le n)\).

Output

• In ra \(n\) số nguyên, trong đó số thứ \(k\) là số dollar Monocarp còn lại sau ngày cuối cùng của kỳ nghỉ nếu cậu sống ở thủ đô trong đúng \(k\) ngày cuối cùng (tức là đến thủ đô vào ngày \((n-k+1)\)).

Example

6
6 6 1 1 6 6

6 0 1 0 4 0

14
3 13 11 12 10 11 10 7 8 14 11 14 8 2

2 6 4 15 7 15 16 6 7 7 9 8 11 16

10
1 2 3 4 5 6 7 8 9 10

10 19 7 16 4 13 1 10 16 1

Nguồn: CodeForces