Šeštadieninė informatikos olimpiadininkų mokykla

Iš čiaupo pilamas vanduo į ilgą ploną akvariumą su įvairiais vertikaliais skirtukais (sienomis). Akvariumas pradžioj yra tuščias, jo dugnas yra visiškai horizontalus. Po kiek laiko vanduo išsipils per kairiausią ar dešiniausią skirtuką?

Čiaupas yra virš taško , o skirtukai yra pozicijose ir . Skirtukai yra įtvirtinti statmenai grindims ir yra įvairių aukščių. Akvariumo ilgis yra didesnis už , sienos aukštesnės už aukščiausią skirtuką, plotis yra 1 vienetas bet kurioje vietoje. Iš čiaupo vanduo teka 1 kubinio vieneto per sekundę greičiu. (Galite laikyti, kad vanduo yra idealus skystis: visada teka žemyn, o jei negali, tai plečiasi visomis horizontaliomis kryptimis vienodu greičiu.)

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai xkaire (neigiamas nelyginis skaičius) ir xdesine (teigiamas nelyginis skaičius). Kitose eilutėse pateikti skirtukų aukščiai (teigiami skaičiai iki 1000000) nuo kairiausio. Skirtukų yra ne daugiau nei 1000.

Rezultatai

Vienoje eilutėje vienas skaičius - laikas sekundėmis, po kurio vanduo pradės tekėti per kairiausią arba dešiniausią skirtuką.

Pavyzdys

-3 3
4
3
2
1

6