贝西和奶牛最近一直在玩“很酷”的序列,并正在尝试构建一些序列。不幸的是他们的算术不好,所以他们需要你的帮助!
如果 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 个元素。