Perica već nekoliko meseci provodi dane kraj računara igrajući igru Jezerca. Na početku igre se na ekranu pojavi pravougaona mreža kvadratića na kojoj je prikazan reljef nekog predela u obliku stubića raznih visina koji se nižu jedan za drugim. Zatim preko cele širine ekrana počinje padati kiša. Ona popunjava udubljenja u reljefu, a višak nestaje na levom i desnom kraju ekrana (tj. na stubićima na levom i desnom kraju se uopšte ne zadržava). Kiša prestaje kada se popune sva udubljenja (tako da sva kiša koja padne odlazi na krajeve ekrana i gubi se). Voda koja je napunila udubljenja obrazuje određen broj jezera (vodene površine odvojene bar jednim vertikalnim stubom od drugih vodenih površina).
Perica u tom trenutku treba da izračuna koliko ima kvadratića popunjenih vodom u onom jezeru u kome se zadržalo najviše vode (tj. ima najviše popunjenih kvadratića). Napiši program koji će Perici pomoći da odredi broj kvadratića u jezeru sa najviše kvadratića.
Ulaz:
U prvom redu standardnog ulaza nalazi se ceo broj n (1 ≤ n ≤ 100000) i to je ukupan broj stubića u reljefu. U svakom od sledećih n redova nalazi se po jedan ceo broj i oni predstavljaju visine stubića u redosledu u kome se oni prikazani na ekranu (od levog kraja prema desnom kraju). Visine stubića su između 1 i 10000.
Izlaz:
U prvi red standardnog izlaza treba ispisati broj kvadratića popunjenih vodom u jezeru u kome ima najviše kvadratića popunjenih vodom. Ako ne postoji niti jedno jezero, štampati broj nula (0).
Primer:
standardni ulaz | standardni izlaz | |
---|---|---|
23 2 3 3 4 2 3 1 3 3 5 2 2 4 6 8 7 4 5 6 3 2 1 1 |
8 |
Objašnjenje:
Slika prikazuje izgled reljefa, kao i raspored jezera nakon popunjavanja svih udubljenja. Kao što se sa slike vidi ima tri jezera koja imaju 8, 7 i 3 popunjena kvadratića.
Comments