Mika i Laza igraju igru kartama. Špil sadrži n karata, pri čemu i-ta karta vredi a_i poena. Oni izvlače karte u redosledu u kome se nalaze u špilu, počevši od dna. I Mika i Laza na početku imaju po 0 poena i svaki put kada neki igrač izvuče kartu, broj njegovih poena se povećava za vrednost te karte. Prvo izvlači Mika, a zatim izvlači onaj igrač koji u tom trenutku ima manje poena. Ako imaju jednak broj poena, izvlači Mika.

Međutim, ono što Laza ne zna a Mika zna je početni raspored karata. Naravno, Mika hoće da vara tako što će preseći špil na nekom mestu i zatim početi igru. Pod sečenjem se podrazumeva standardno sečenje: izabere se proizvoljna pozicija u špilu i sve karte iznad te pozicije se prebace na dno špila, ne menjajući međusobni poredak. Odrediti koliko najviše poena može osvojiti Mika varanjem i na koliko načina može to postići.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalazi se prirodan broj n ≤ 10⁵ - broj karata u špilu. Sledeći red sadrži n prirodnih brojeva a_i - vrednosti karata (a_i≤ 200). Karte su date u redosledu od dna do vrha špila.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlazne datoteke ispisati dva broja razdvojena razmakom - maksimalan broj poena koje Mika može osvojiti nekim sečenjem i broj načina na koji on to može postići, redom.

Primer 1:

5
2 3 4 5 1

9 2

Objašnjenje.

Ako Mika preseqe posle treće ili posle četvrte karte (2 načina), on osvaja maksimalnih 9 poena.

Napomena.

U 10% test primera n ≤ 10³.