Vegetable Bed Filling Problem

Given a line of \(N\) vegetable beds, some of which are already planted with a vegetable (represented by a positive integer) and the rest are empty (represented by \(0\)), your task is to determine the minimum number of distinct vegetable types that need to be used to fill all the empty beds so that no two adjacent beds contain the same type of vegetable.

More formally, you are given an array \(beds\) of length \(N\) where each element is either \(0\) (empty) or a positive integer (already planted). For every contiguous segment of empty beds, you must assign a vegetable type that is different from the types of the adjacent pre-planted beds. It is guaranteed by the problem constraints that for all provided test cases the answer is 1.

Note: Although a non-trivial coloring might be required for some sequences, the given test cases are designed in a way that using a single new vegetable type will always be sufficient.

inputFormat

The first line contains an integer \(N\) \( (1 \leq N \leq 10^5)\), the number of vegetable beds.

The second line contains \(N\) space-separated integers. Each integer is either a positive number indicating an already planted vegetable or \(0\) indicating an empty bed.

Input is read from standard input (stdin).

outputFormat

Output a single integer representing the minimum number of distinct vegetable types needed to fill all the empty beds such that no two adjacent beds (including both pre-planted and newly planted ones) contain the same type. Output is written to standard output (stdout).

6
1 0 2 0 3 4

1