Metsälän ja Syrjälän välinen uusi metroyhteys on viimein avattu. Linjalla on n asemaa, joista ensimmäinen on Metsälä ja viimeinen on Syrjälä.

Metro ajoi ensimmäisen vuoron Metsälästä Syrjälään. Tiedät jokaisesta asemasta, montako matkustajaa yhteensä nousi junaan tai poistui junasta. Mikä on näiden tietojen perusteella pienin ja suurin mahdollinen määrä, montako matkustajaa oli enimmillään junassa jonkin kahden aseman välillä?

Juna oli tyhjä matkan alussa ja lopussa sekä kukaan matkustaja ei poistunut junasta heti nousemisen jälkeen samalla asemalla.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: asemien määrä.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: mittaustulos kullakin asemalla.

Tuloste

Tulosta kaksi kokonaislukua: ala- ja yläraja junan suurimmalle matkustajamäärälle.

Voit olettaa, että on ainakin yksi tapa, miten matkustajat ovat voineet liikkua.

Esimerkki

Syöte:

4
5 3 4 6

Tuloste:

6 8

Selitys: Alarajassa junassa on asemien välillä 5, 2 ja 6 matkustajaa. Ylärajassa junassa on asemien välillä 5, 8 ja 6 matkustajaa.

Osatehtävä 1 (14 pistettä)

• 2 \le n \le 10
• 1 \le x_i \le 10

Osatehtävä 2 (28 pistettä)

• 2 \le n \le 100
• 1 \le x_i \le 10

Osatehtävä 3 (58 pistettä)

• 2 \le n \le 10^5
• 1 \le x_i \le 10^9