CF2242F Summer Vacation

While reading the statement of this problem, we recommend forgetting that summer consists of $ 92 $ days and that a day consists of $ 1440 $ minutes. This is Berland, and things are different here. Monocarp is a student at a provincial university in Berland. The summer holidays have just begun, and they will last for the next $ n $ days. Monocarp has long dreamed of going to the capital of Berland, so he will choose one day $ i $ among these days, arrive in the capital on that day, and spend the rest of the holidays there. The capital of Berland is not a very cheap city, and Monocarp has $ 0 $ Berland dollars with him. Naturally, this is not enough to visit interesting places and buy souvenirs. Therefore, on some days in the capital, Monocarp will work as a freelancer. He does not want to work in his hometown, since he has already spent the whole academic year doing university assignments. Formally, on the $ i $ -th day of the holidays, Monocarp will have $ a_i $ free minutes, which he will spend either working or resting and buying souvenirs. If Monocarp has at least $ a_i $ dollars at the beginning of the $ i $ -th day, then on that day he will spend them on rest and souvenirs at a rate of $ 1 $ dollar per minute; that is, during this day, he will spend $ a_i $ dollars. Otherwise, he will spend this time working, earning $ 1 $ dollar per minute; that is, during this day, he will earn $ a_i $ dollars. Note that Monocarp always makes his decision for the entire day; it is impossible for him to both spend and earn money during the same day. Your task is to determine, for each number of days $ k $ from $ 1 $ to $ n $ , how many dollars Monocarp will have left after the last day of the holidays if he lives in the capital for exactly $ k $ last days (i. e. if he arrives on the day $ (n-k+1) $ ).

The first line contains one integer $ n $ ( $ 1 \le n \le 10^{5} $ ). The second line contains $ n $ integers $ a_{i} $ ( $ 1 \le a_{i} \le n $ ).

Print $ n $ integers, where the $ k $ -th integer must be equal to the number of dollars Monocarp will have left if he lives in the capital for exactly $ k $ last days (i. e. if he arrives on the day $ (n-k+1) $ ).