Arhitektu birojam „Tasja & Esabruks” ir uzdots projektēt daudzstāvu viesnīcu kompleksu slavenā piejūras kūrortā. Viesnīcu būvei ir atvēlēta vien šaura zemes strēle N vienību garumā, kas stiepjas gar jūru un ko abos galos ierobežo stāvas klintis, pie kam katrā vienībā drīkst būvēt ne vairāk kā vienu viesnīcu. Shematiski katru viesnīcu var aprakstīt kā naturāla augstuma stabiņus uz veselo skaitļu ass, uz kuras atzīmētas N vienības, kas sanumurētas pēc kārtas ar skaitļiem no 1 līdz N:

Tā kā paredzētais viesnīcu blīvums ir visai liels, ir svarīgi noteikt, cik daudz gaismas nokļūs katras viesnīcas stāva logos. Visu viesnīcu stāvi ir vienādi augsti un katram no tiem tiek aprēķināts labums, kas tiek izteikts iepriekšminētajās garuma vienībās. Ja viesnīcu paredzēts būvēt vienībā i(1≤i≤N), tad tās j-tā(1≤j) stāva labumu aprēķina vispirms uz katru pusi atrodot tuvāko objektu, kas ir vismaz j stāvus augsts (pietiekami augsta viesnīca vai klints) un izvēloties lielāko no šiem attālumiem. Aprēķinos tiek uzskatīts, ka klintis atrodas vienībās 0 un N+1, pie kam tās ir augstākas par visaugstāko iespējamo viesnīcu. Zīmējumā katrā rūtiņā ierakstītais skaitlis ir attiecīgā viesnīcas stāva labums.

Uzrakstiet programmu, kas plānotam viesnīcu izvietojumam un katras viesnīcas stāvu skaitam, aprēķina katras viesnīcas visu stāvu kopējo labumu!

Pirmajā rindā dots naturāls skaitlis N(N≤10⁵ , zemes strēles garums garuma vienībās). Otrajā rindā doti N veseli nenegatīvi skaitļi. Katram i(1≤i≤N) i-tais skaitlis šajā rindā apzīmē tās viesnīcas, ko paredzēts būvēt i-tajā vienībā, stāvu skaitu. 0 nozīmē, ka viesnīcu šajā vienībā būvēt nav paredzēts. Neviena viesnīcas augstums nepārsniedz 10⁹ . Starp katriem diviem blakus skaitļiem ievaddatos ir viena tukšumzīme.

Pirmajā rindā jāizvada tik skaitļi, cik viesnīcu ir aprakstīts ievaddatos. Šiem skaitļiem jāapraksta viesnīcu labumi pēc kārtas vienību numuru pieaugšanas secībā. Starp katriem diviem blakus skaitļiem izvaddatos jābūt tukšumzīmei.

Uzdevums izmantots LIO 2015. gada atlases kārtā