Mutation

Genetic scientists of the planet Olympia are again experimenting with the DNA of primitive organisms. The genome of an organism is a sequence of genes, each of which can be encoded with one positive integer. Genes that are encoded by the same numbers are considered the same, and vice versa, genes that are encoded by different numbers are considered different.

Scientists have already deduced some primitive organism and want to modify its genome in such a way as to obtain an ideal organism. They believe that in the future it will help to find a cure for many diseases.

An organism is considered ideal if any two identical genes are either located in adjacent positions in the genome, or there is at least one the same gene between them.

In one operation, scientists can select and remove one or more identical genes from the body's genome, after which they can be inserted back into the genome, but perhaps in different positions. Since each such operation weakens the body, scientists want to achieve their goal, while performing as few operations as possible.

Write a program that, according to a given representation of the genome, will determine the smallest number of operations necessary to obtain an ideal organism.

Input

The first line contains the number of genes $n(1\le n\le 10^5)$ in the genome of the primitive organism. The next line contains $n$ positive integer, each does not exceed $n$ — the sequence of genes in the genome.

Output

Print the least number of operations for which scientists can get a perfect organism.

Examples