俗話說「樹大必有枯枝」，園藝用的造景樹可能很大，可能會包含很多枯枝。 如果一棵樹的枯枝程度過高，會影響到整棵樹的美觀，因此我們打算以一棵樹的 「枯枝程度」作為評估美觀程度的依據之一。 園藝用造景樹通常會被修剪成每段樹枝最多只會有 2 個分叉的模樣(即二元 樹)，假設已知每段樹枝的枯枝值，則某段樹枝的「子樹枯枝程度」定義為下面 的式子: 子樹枯枝程度 = max(左子樹枯枝程度 , 右子樹枯枝程度 ) + 根樹枝枯枝值 其中若該樹枝的左/右子樹不存在，則其左/右子樹的枯枝程度視為 0。根樹枝的

子樹枯枝程度即為整棵樹的「枯枝程度」。

小懶是個懶惰的園丁，他對於每天反覆計算園藝用造景樹的枯枝程度已經感 到厭煩了，於是他決定將評估枯枝程度的工作委託給其他人來做。即使是委託給 其他人來進行，小懶還是得提供園藝用造景樹的模樣與各段樹枝的枯枝值;但是 小懶實在太懶惰了，所以他想出了一種能夠更加簡化的方法，那就是依照園藝用 造景樹的「前序走訪」記錄各段樹枝的枯枝值，這樣一來就能夠使用一個序列來 同時表示各段樹枝的枯枝值與園藝用造景樹的模樣，小懶對此甚是滿意並開始委 託工作。 圖一:圖中節點內的數值代表各段樹枝的枯枝值，並假設最上方節點為根，其整體枯枝程度為 6，「前序走訪」序列為 [1, 2, 3, 2, 3, 1]。 但此方法存在一個致命性的問題，那就是只記錄園藝用造景樹的「前序走訪」 序列無法還原出唯一園藝用造景樹的模樣，因為可能存在不同模樣的園藝用造景 樹擁有同樣的「前序走訪」序列，所以也就無法正確評估樹的枯枝程度。

你就是小懶所委託的那個人，請你在只知道依「前序走訪」所記錄各段樹
枝枯枝值序列的情況下，在所有滿足條件的園藝用造景樹之中，評估其整棵樹
枯枝程度的最小值與最大值可能為多少?

輸入格式

第一行輸入 1 個正整數 N (1 ≤ N ≤ 1,000)，表示園藝用造景樹有 N 段樹枝。 第二行包含 N 個非負整數 di (0 ≤ di ≤ 109) 的序列，表示園藝用造景樹依「前序 走訪」記錄各段樹枝其枯枝值的序列。

輸出格式

為兩個整數值，分別代表對於滿足條件的園藝用造景樹中，其可能的枯枝程 度最小值與最大值。

範例輸入

7 
3 1 1 0 2 0 5

範例輸出

8 12