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