D. Численность населения
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разрабатывает интересную теорию о взаимосвязи арифметических прогрессий со всем-всем-всем в мире. Текущая идея икс состоит в том, что численность населения столицы Берляндии изменяется со временем как арифметическая прогрессия. Ну или несколько арифметических прогрессий.

Поликарп считает, что если выписать численность населения столицы для нескольких подряд идущих лет в последовательность a1, a2, ..., an, то удобно рассматривать этот массив как несколько арифметических прогрессий, записанных друг за другом. Например, последовательность (8, 6, 4, 2, 1, 4, 7, 10, 2) можно рассматривать как последовательность трёх арифметических прогрессий (8, 6, 4, 2), (1, 4, 7, 10) и (2), которые записаны подряд друг за другом.

К сожалению, Поликарп может и не располагать всеми данными за n последовательных лет (ведь не каждый год делается перепись населения). По этой причине некоторые значения ai могут быть неизвестны. Такие значения он обозначает числом -1.

По заданной последовательности a = (a1, a2, ..., an), которая состоит из положительных целых чисел и значений -1, найдите минимальное количество арифметических прогрессий, чтобы получить a. Для получения a прогрессии надо записать последовательно одну за другой. Значениям -1 может соответствовать произвольное положительное целое число, а значения ai > 0 должны быть точно равны соответствующим элементам искомой последовательной записи прогрессий.

Напомним, что конечная последовательность c называется арифметической прогрессией, если разность ci + 1 - ci любых двух последовательных элементов в ней является константой. По определению, любая последовательность длины 1 — это арифметическая прогрессия.

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 2·105) — количество элементов в последовательности. Во второй строке записаны целочисленные значения a1, a2, ..., an через пробел (1 ≤ ai ≤ 109 или ai =  - 1).

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

Выведите наименьшее количество арифметических прогрессий, которые надо записать одну за другой, чтобы получить последовательность a. На месте значений -1 в a могут быть любые положительные целые числа.

Примеры
Входные данные
9
8 6 4 2 1 4 7 10 2
Выходные данные
3
Входные данные
9
-1 6 -1 2 -1 4 7 -1 2
Выходные данные
3
Входные данные
5
-1 -1 -1 -1 -1
Выходные данные
1
Входные данные
7
-1 -1 4 5 1 2 3
Выходные данные
2