Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Геометрическая задача
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп очень любит геометрические прогрессии — он их коллекционер. Но так как такие прогрессии попадаются крайне редко, то ему очень нравятся и такие последовательности чисел, в которых можно удалить один элемент, что в результате получается геометрическая прогрессия.

В этой задаче геометрическими прогрессиями будем называть такие конечные последовательности чисел a1, a2, ..., ak, что ai = c·bi - 1 для некоторых вещественных чисел c и b. Например, последовательности [2, -4, 8], [0, 0, 0, 0], [199] — геометрические прогрессии, а [0, 1, 2, 3] — нет.

Недавно Поликарпу попалась последовательность и он никак не может ее классифицировать. Помогите ему в этом. Определите, является ли она геометрической прогрессией. Если нет, то проверьте, можно ли удалить из нее один элемент так, чтобы в результате она стала геометрической прогрессией.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество чисел в заданной последовательности. Вторая строка содержит заданную последовательность. Числа разделяются пробелами. Все элементы заданной последовательности — целые, не превосходящие по абсолютной величине 104.

Выходные данные

Выведите 0, если заданная последовательность является геометрической прогрессией. В противном случае проверьте, верно ли, что можно удалить один элемент так, чтобы она стала геометрической прогрессией. Если это так, то выведите 1. В случае, если это сделать невозможно, выведите 2.

Примеры
Входные данные
4
3 6 12 24
Выходные данные
0
Входные данные
4
-8 -16 24 -32
Выходные данные
1
Входные данные
4
0 1 2 3
Выходные данные
2