Mutation#4973
Genetic scientists from the planet Olympia are once again conducting experiments with the DNA of primitive organisms. The genome of an organism is a sequence of genes, each of which can be encoded by a natural number. Genes encoded by the same number are considered identical, while genes encoded by different numbers are considered different.
The scientists have already created a primitive organism and want to modify its genome in such a way as to produce an ideal organism. They believe that this will help develop cures for many diseases in the future.
An organism is considered ideal if any two identical genes are either located on adjacent positions in the genome or have at least one identical gene between them.
In one operation, scientists can select one or more identical genes in the genome, remove them, and then place them back into the genome, possibly at different positions. Since each such operation weakens the organism, the scientists aim to minimize the number of operations needed to achieve their goal.
Write a program that, given a representation of the genome, determines the minimum number of operations required to create an ideal organism.
The first line contains the number of genes n~(1 \le n \le 10^5) in the genome of a primitive organism. The second line contains positive integers, each of which does not exceed — the sequence of genes in the genome.
Print the minimum number of operations required to create an ideal organism.
Example 1