Modern Art 1D: Moonet's Minimum Rounds

Picowso has switched to a minimalist, 1-dimensional style. Her painting is represented by an array of colors of length \(N\) (where \(1 \leq N \leq 100{,}000\)). She originally paints by layering intervals of color over a blank canvas using each of the colors \(1, 2, \ldots, N\) exactly once, though some colors may eventually be completely covered.

Moonet, her rival, plans to replicate the final painting using a process in which he paints a set of disjoint intervals in each round. Note that he may only paint one interval for each color throughout the process. To duplicate the painting, for every color that appears in the final work, consider the interval spanning from its first occurrence to its last occurrence. Since these intervals may overlap, Moonet must schedule them in different rounds if they overlap.

Your task is to compute the minimum number of rounds needed for Moonet to cover all such intervals. Equivalently, this number is the maximum number of overlapping intervals at any position of the painting.

For example, if the painting is represented by the array [1, 2, 1], then the interval for color 1 is from index 1 to 3 and that for color 2 is [2, 2]; the maximum overlap is 2.

inputFormat

The first line contains a single integer \(N\) denoting the length of the painting.

The second line contains \(N\) space-separated integers. The \(i\)-th integer indicates the color at position \(i\) in the final painting.

outputFormat

Output a single integer: the minimum number of rounds needed for Moonet to replicate Picowso's painting.

sample

3
1 2 1

2