Binge watching
Ben versucht, die Zeit, die er mit Filmschauen verbringt, so weit wie möglich zu maximieren. Er weiß, dass in den nächsten Tagen
n Filme im Fernsehen laufen werden und kennt die Spieldauer jedes einzelnen. Wir wissen, dass Ben nicht länger als 5 Stunden (18000 Sekunden) am Stück Filme schauen kann und danach einschläft. Er zählt nur die Filme, die er von Anfang bis Ende vollständig gesehen hat. Wenn er also mitten im Film einschläft, wird dieser Film nicht mitgezählt.
Kannst du ihm helfen, den optimalen Zeitpunkt zu finden, um mit dem Schauen zu beginnen? Zeige ihm dafür, wie viele Sekunden er bei einem Start ab dem
i-ten Film vollständig sehen kann.Eingabe
Die erste Zeile der Eingabe enthält die ganze Zahl
n, also die Anzahl der Filme (1 ≤ n ≤ ). Die nächste Zeile enthält n ganze Zahlen, jeweils getrennt durch ein Leerzeichen, die die Länge der Filme in Sekunden angeben (1 ≤ ≤ 15000).Ausgabe
Das Programm soll
n ganze Zahlen ausgeben. An der Stelle i soll dabei die Anzahl der Sekunden stehen, die Ben vollständig sehen kann, wenn er beim Film i anfängt.Beispiele
Input | Output |
8
12000 3000 9000 12000 13200 13800 3600 5400 | 15000 12000 9000 12000 13200 17400 9000 5400 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB