题目描述

现在给你一个长度为 $n$ 的整数序列 $A$。你可以对序列中任意一个 $a_i(1\le i \le n)$ 进行如下操作：

你可以任意选择一个整数 $j(j>0)$，使 $A_i$ 加上 $\sum_{k=0}^{j-1}3^k$。如果记这个累加后的数为 $B_i$，我们就可以得到一个新数列 $B$。

显然，你有无穷多的方案可以使 $B$ 序列单调递增。

我们定义一个方案的代价为这个方案所有所选择的 $j$ 中的 $j$ 的最大值。

对于那么多的方案中，现在你需要找到一种方案让 $B$ 序列单调递增时，这种方案的代价最小。

注意你应该对每个数进行一次操作。

输入格式

第一行一个整数 $n$ 表示 $A$ 序列的长度。
第二行共 $n$ 个整数表示 ${A_1, A_2, A_3\dots A_n}$。

输出格式

一行一个整数表示答案。

5
1 5 3 7 13

2

样例说明 1

对于其中一种方案，当选择的 $j$ 为 $1,1,2,1,1$ 时，$B$ 序列为 $2,6,7,8,14$，符合条件。此时 $j$ 能取到最小值 $2$。

2
1000000000 1

20

数据规模与约定

对于 $10\%$ 的数据，$n \leq 3$，$|A_i|\leq 100$。
对于 $50\%$ 的数据， $n \leq 5\times10^6$，$|B_i|\leq 10^9$。
对于 $100\%$ 的数据, $2\le n \leq 5\times10^6$，$|A_i| \leq 10^9$。