CF1481E.Sorting Books

One day you wanted to read something, so you went to your bookshelf to grab some book. But when you saw how messy the bookshelf was you decided to clean it up first.

There are $n$ books standing in a row on the shelf, the $i$-th book has color $a_i$.

You'd like to rearrange the books to make the shelf look beautiful. The shelf is considered beautiful if all books of the same color are next to each other.

In one operation you can take one book from any position on the shelf and move it to the right end of the shelf.

What is the minimum number of operations you need to make the shelf beautiful?

有一天，你想读点东西，于是走到书架前想拿一本书。但当你看到书架乱糟糟的样子时，决定先整理一下。

书架上从左到右一排摆放着 $n$ 本书，其中第 $i$ 本书的颜色为 $a_i$。

你希望重新排列这些书，使书架看起来美观。当且仅当所有颜色相同的书都彼此相邻（即形成一个连续的块）时，书架才被视为美观。

每次操作中，你可以从书架的任意位置取出一本书，并将其放到书架最右端。

请问：要使书架变得美观，最少需要多少次操作？

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of books.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the book colors.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——书籍的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）——书籍的颜色。

Output the minimum number of operations to make the shelf beautiful.

输出使书架变得美观所需的最少操作次数。

In the first example, we have the bookshelf $[1, 2, 2, 1, 3]$ and can, for example:

1. take a book on position $4$ and move to the right end: we'll get $[1, 2, 2, 3, 1]$;
2. take a book on position $1$ and move to the right end: we'll get $[2, 2, 3, 1, 1]$.

In the second example, we can move the first book to the end of the bookshelf and get $[2,2,1,1,1]$.

在第一个例子中，书架为 $[1, 2, 2, 1, 3]$，例如可以：

1. 将位置 $4$ 上的书移至最右端：得到 $[1, 2, 2, 3, 1]$；
2. 将位置 $1$ 上的书移至最右端：得到 $[2, 2, 3, 1, 1]$。

在第二个例子中，我们可以将第一本书移到书架末端，得到 $[2,2,1,1,1]$。