Directorul şcolii noastre are obiceiul să împartă bomboane: la Crăciun, de 1 iunie, la Paşte sau în fiecare zi.
Pe masa din cabinetul lui este un coş mare în care se află bomboane. Fiecare persoană care intră la el în cabinet este invitată, la plecare, să ia bomboane din coş.
Astăzi a împărţit bomboanele într-un mod mai ciudat. Mai exact, în cabinet au intrat N persoane, pe care pentru simplitate le vom numerota în ordinea intrării de la 1 la N. La plecare fiecare persoană i (1≤i≤N) este invitată să ia din coş jumătate dintre bomboanele existente în coş+ încă nri bomboane. Dacă numărul de bomboane din coş este impar, atunci persoana i poate lua ″jumătatea″ mai mică sau ″jumătatea″ mai mare, după plac.
De exemplu, dacă în coş sunt 20 de bomboane şi nr1=1, iar nr2=3, atunci persoana 1 va lua 10 bomboane+1=11. În coş rămân 9 bomboane. Persoana 2 poate lua 4+3 bomboane sau 5+3 bomboane, după plac.
Secretara observă că la sfârşitul zilei coşul este gol. Ea se întreabă câte bomboane au fost în coş, dar, evident că nu ştie cum au ales să ia bomboane persoanele pentru care numărul de bomboane din coş era impar.
Cerinţă
Scrieţi un program care să determine numărul maxim şi numărul minim de bomboane ce ar fi putut fi în coş.
Date de intrare
Fişierul de intrare cos.in conţine pe prima linie numărul natural N, iar pe a doua linie N numere naturale separate prin câte un spaţiu nr1 nr2 ...nrN, cu semnificaţia din enunţ.
Date de ieşire
Fişierul de ieşire cos.out va conţine două linii. Pe prima linie va fi scris numărul maxim de bomboane ce ar fi putut fi în coş, iar pe a doua linie numărul minim de bomboane ce ar fi putut fi în coş.
Restricţii
• 1 ≤ N ≤ 1000
• 0 ≤ nri ≤ 1000, pentru 1≤i≤N
• Rezultatele au cel mult 500 de cifre.
Exemple
cos.in
cos.out
Explicaţii
2
1 3
17
11
Numărul maxim de bomboane ce se pot află în coş este 17.
Persoana 1 ia (17+1)/2+1=10 bomboane. Rămân 7 bomboane.
Persoana 2 ia (7+1)/2+3 bomboane. Coşul rămâne gol.
Numărul minim de bomboane ce se pot află în coş este 11:
Intră persoana 1 ia 11/2=5 bomboane +1. Rămân 5 bomboane
Persoana 2 ia 5/2+3. Coşul e gol.