← 返回题目列表

Codeforces · 51/D

D. 几何问题

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

坡旅甲喜欢几何级数——他收集它们。然而,由于这种级数很少发生,他也喜欢数字序列,删除单个元素就足以获得几何级数。

在此任务中,我们将几何级数定义为数字 a1、a2、...、ak 的有限序列,其中对于某些实数 c 和 b,ai = c·bi - 1。例如,序列 [2, -4, 8]、[0, 0, 0, 0]、[199] 是等比级数,而 [0, 1, 2, 3] 则不是。

最近Polycarp发现了一个序列,但他无法对其进行分类。帮助他做到这一点。判断是否是等比级数。如果不是,检查删除一个元素后是否可以变成等比级数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 给定序列中的元素数量。第二行包含给定的序列。数字以空格分隔。给定序列的所有元素都是整数,并且它们的绝对值不超过104。

输出

如果给定序列是等比级数,则打印 0。否则,检查是否可以通过删除单个元素使序列成为几何级数。如果可以,则打印1。如果不可能,则打印2。

示例

输入 #1

4
3 6 12 24

输出 #1

0

输入 #2

4
-8 -16 24 -32

输出 #2

1

输入 #3

4
0 1 2 3

输出 #3

2