ACM Новосибирск 2013
Кубичность
Исследовательский космический спутник в ходе изучения некоторой функциональной зависимости произвел n измерений. Чтобы передать результаты эксперимента на Землю в наиболее сжатом виде, требуется разбить всю область значений аргумента на минимальное количество отрезков с соблюдением следующего условия: на каждом из этих отрезков должен существовать полином не более чем третьей степени, совпадающий с результатами измерений во всех точках, принадлежащих этому отрезку.
Также необходимо, чтобы границы получившихся отрезков являлись точками исходных измерений.
Input data
В первой строке находится количество измерений n (2 ≤ n ≤ 100). В следующей строке заданы n пар целых чисел, каждое из которых по модулю не превышает 1000, – результаты проведенных измерений. В каждой такой паре первое число – значение аргумента, а второе – соответствующее значение функции в этой точке. Пары перечислены в порядке возрастания координаты, расстояние между точками измерений не превышает 100. Числа в строке разделены не менее чем одним пробелом.
Output data
Вывести минимально возможное число отрезков.
Examples
10 0 0 1 1 2 2 3 3 4 4 5 4 6 4 7 4 8 4 9 4
2