题目描述
现在给你一个长度为 n 的整数序列 A。你可以对序列中任意一个 ai(1≤i≤n) 进行如下操作:
你可以任意选择一个整数 j(j>0),使 Ai 加上 ∑k=0j−13k。如果记这个累加后的数为 Bi,我们就可以得到一个新数列 B。
显然,你有无穷多的方案可以使 B 序列单调递增。
我们定义一个方案的代价为这个方案所有所选择的 j 中的 j 的最大值。
对于那么多的方案中,现在你需要找到一种方案让 B 序列单调递增时,这种方案的代价最小。
注意你应该对每个数进行一次操作。
输入格式
第一行一个整数 n 表示 A 序列的长度。
第二行共 n 个整数表示 A1,A2,A3…An。
输出格式
一行一个整数表示答案。
样例说明 1
对于其中一种方案,当选择的 j 为 1,1,2,1,1 时,B 序列为 2,6,7,8,14,符合条件。此时 j 能取到最小值 2。
数据规模与约定
对于 10% 的数据,n≤3,∣Ai∣≤100。
对于 50% 的数据, n≤5×106,∣Bi∣≤109。
对于 100% 的数据, 2≤n≤5×106,∣Ai∣≤109。