← 返回题目列表

Codeforces · 283/D

D. 奶牛和酷序列

中文机器翻译题面 查看原题

贝西和奶牛最近一直在玩“很酷”的序列,并正在尝试构建一些序列。不幸的是他们的算术不好,所以他们需要你的帮助!

如果 x 可以表示为 y 个连续整数(不一定是正数)的和,则一对 (x, y) 正整数是“酷”的。如果 (a1, a2), (a2, a3), ..., (an - 1, an) 都是很酷的,那么序列 (a1, a2, ..., an) 就是“酷”。

奶牛有一个由 n 个正整数组成的序列,a1, a2, ..., an。在一步中,他们可能会用任何其他正整数替换某些 ai(对 ai 的新值没有其他限制)。确定使结果序列冷却所需的最少移动次数。

输入

第一行包含一个整数 n (2 ≤ n ≤ 5000)。下一行包含 n 个空格分隔的整数,a1, a2, ..., an (1 ≤ ai ≤ 1015)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

一个整数,为使序列变酷而必须更改的 ai 的最小数量。

示例

输入 #1

3
6 4 1

输出 #1

0

输入 #2

4
20 6 3 4

输出 #2

2

注意

在第一个示例中,序列已经很酷,因此我们不需要更改任何元素。在第二个示例中,我们可以将 a2 更改为 5,将 a3 更改为 10 来生成 (20, 5, 10, 4),这很酷。这改变了 2 个元素。