坡旅甲喜欢几何级数——他收集它们。然而,由于这种级数很少发生,他也喜欢数字序列,删除单个元素就足以获得几何级数。
在此任务中,我们将几何级数定义为数字 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