题目描述

​ 梦梦很有钱。 ​ 梦梦有 n 堆鸽子蛋那么大的宝石，其中第 i 堆里面有 $h_i$ 粒鸽子蛋那么大的宝石。 ​ 熊熊也想要鸽子蛋那么大的宝石，梦梦答应把 n 堆鸽子蛋那么大的宝石中最少的那一堆送给他。 ​ 梦梦允许熊熊进行以下操作： ​ 从第 3 堆宝石开始从前往后进行操作。设当前为第 i 堆宝石，你可以选择一个在 $[0,\frac {h_i}3]$ 的整数 d，从第 i 堆宝石中取出 3d 粒宝石，然后往第 i-1 堆宝石里放入 d 粒宝石，往第 i-2 堆宝石里放入 2d 粒宝石。 ​ 你需要通过合理设计操作方案，使得数量最少的一堆宝石的数量最大。请求出这个最大值。 ​

输入格式

​ 一行，一个正整数 n。 ​ 第二行，包含 n 个正整数 $h_i$。 ​

输出格式

​ 一行，一个整数，表示答案。 ​

样例

​

样例输入

​

4
1 2 10 100

​

样例输出

​

7

​

样例解释

​ i=3 时，取 d=3，i=4 时，取 d=7 即可构造出最大答案。 ​

数据范围与提示

​ 对于 30\% 的数据，1 \leq n\leq 10^3。 ​ 对于 100\% 的数据，1 \leq n \leq 10^5,1 \leq h_i \leq 10^9。 ​