George 非常热爱信息学，但他还是一名初学者，因此他需要你的帮助。
在信息学课上，老师在黑板上写下了 $N$ 个整数，George 需要进行若干次操作。每次操作包括选择两个相邻的整数，并将它们替换为一个数字，该数字等于它们算术平均值的整数部分。例如，7 和 9 被替换为 8，7 和 12 被替换为 9，101 和 102 被替换为 101。George 需要不断进行这些操作，直到黑板上只剩下一个整数为止。
帮助 George 找出最终能得到的最大数字。
输入格式
第一行包含一个整数 $N$，表示黑板上数字的个数。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_n$，表示最初写在黑板上的数字。
输出格式
第一行包含一个整数，表示在进行所有操作后，最终能得到的最大数字。
数据范围
- $1 \le N \le 200$
- $1 \le a_i \le 1,000,000,000$，对于 $1 \le i \le N$
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 30 分 | $N < 10$ |
| 2 | 70 分 | $N \le 200$ |
样例
输入格式 1
4 2 4 5 7
输出格式 1
5
说明
初始黑板上的数字：2 4 5 7 替换位置 2 和 3 的元素：2 4 7 替换位置 1 和 2 的元素：3 7 替换位置 1 和 2 的元素：5