Maximal Valid Cuts in a Colored Triangulated Polygon

This problem is adapted from BalticOI 2009 Day2 T2 Triangulation.

We are given a convex polygon that has been triangulated. Recall that a triangulation of a polygon is a collection of triangles whose vertices are also vertices of the polygon, such that the triangles do not overlap and together cover the entire polygon. In our problem, the polygon is convex and the triangulation is given in the form of a fan: if the polygon has $n$ vertices then it has exactly $n-2$ triangles, namely the triangles (1, i, i+1) for $i = 2,3,\dots,n-1$.

Each triangle is assigned a color (represented by an integer). A cut is defined as a straight line that splits the polygon into two parts. A cut is valid if and only if for every color, all triangles of that color lie entirely in one of the parts; in other words, no color appears in triangles on both sides of the cut.

Your task is to determine the maximum number of cuts that can be made simultaneously (i.e. choosing a set of non-intersecting cuts) so that for each cut, the two resulting parts do not share any color.

Note that since the triangulation in a convex polygon with a fan structure produces a chain of triangles, each potential cut corresponds to splitting this chain into a prefix and a suffix. Formally, if we denote the colors of the triangles by an array $C$ of length $n-2$, then a cut between indices $i$ and $i+1$ (with $1 \le i < n-2$) is valid if and only if

$$S_1 \cap S_2 = \emptyset,$$

where

$$S_1 = \{ C_1, C_2,\dots,C_i \} \quad\text{and}\quad S_2 = \{ C_{i+1}, C_{i+2},\dots, C_{n-2} \}. $$

inputFormat

The input consists of two lines. The first line contains a single integer $n$ ($n \ge 3$) representing the number of vertices of the convex polygon. The polygon is triangulated in a fan from vertex 1, hence there are exactly $n-2$ triangles.

The second line contains $n-2$ space-separated integers. The i-th integer represents the color of the triangle formed by vertices $(1, i+1, i+2)$.

outputFormat

Output a single integer: the maximum number of valid cuts that can be made such that for each cut, the two parts do not contain the same color.

sample

5
1 2 1

0