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

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

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

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

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