Кубичность
Исследовательский космический спутник в ходе изучения некоторой функциональной зависимости произвел n измерений. Чтобы передать результаты эксперимента на Землю в наиболее сжатом виде, требуется разбить всю область значений аргумента на минимальное количество отрезков с соблюдением следующего условия: на каждом из этих отрезков должен существовать полином не более чем третьей степени, совпадающий с результатами измерений во всех точках, принадлежащих этому отрезку.
Также необходимо, чтобы границы получившихся отрезков являлись точками исходных измерений.
Входные данные
В первой строке находится количество измерений n (2 ≤ n ≤ 100). В следующей строке заданы n пар целых чисел, каждое из которых по модулю не превышает 1000, – результаты проведенных измерений. В каждой такой паре первое число – значение аргумента, а второе – соответствующее значение функции в этой точке. Пары перечислены в порядке возрастания координаты, расстояние между точками измерений не превышает 100. Числа в строке разделены не менее чем одним пробелом.
Выходные данные
Вывести минимально возможное число отрезков.