时间限制：1秒　　内存限制：256M

---

【问题描述】

　　我们来玩一个游戏：\(n\) 个自然数列成一排，你可以从中取走任意多个数，但是相邻的两个不可以同时被取走。
请你计算共有多少种取法 和 能取得数和的最大值。

【输入格式】

　　第 \(1\) 行一个整数 \(n\)，接下来的一行有 \(n\) 个自然数 \(a_i\)。

【输出格式】

　　第 \(1\) 行一个整数表示取法总数.
　　第 \(2\) 行一个整数，表示取得数的最大值。

【输入输出样例1】

　Input

5
1 6 3 4 5

　Output

13
11

【数据限制】

　\(1 ≤ n ≤ 60\)
　\(1 ≤ a_i ≤ 1000\)

【来源】

　　Mr.he