Codeforces Beta Round 48 |
---|
Закончено |
Поликарп очень любит геометрические прогрессии — он их коллекционер. Но так как такие прогрессии попадаются крайне редко, то ему очень нравятся и такие последовательности чисел, в которых можно удалить один элемент, что в результате получается геометрическая прогрессия.
В этой задаче геометрическими прогрессиями будем называть такие конечные последовательности чисел 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
Название |
---|