CF1481E Sorting Books

有一天你想读点什么，于是你走到你的书架前去拿一本书。但当你看到书架有多乱时，你决定先把它整理一下。 书架上有 $n$ 本书排成一排，第 $i$ 本书的颜色为 $a_i$。 你想重新排列这些书，使书架变得美观。如果所有颜色相同的书都相邻放置，则认为书架是美观的。 每次操作你可以从书架上的任意位置取下一本书，并将其移动到书架的最右端。 你需要的最少操作次数是多少，才能使书架变得美观？

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示书的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示每本书的颜色。

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

在第一个样例中，书架为 $[1, 2, 2, 1, 3]$，可以这样操作： 1. 取第 $4$ 本书放到最右端，得到 $[1, 2, 2, 3, 1]$； 2. 取第 $1$ 本书放到最右端，得到 $[2, 2, 3, 1, 1]$。 在第二个样例中，可以将第一本书移动到书架末尾，得到 $[2,2,1,1,1]$。 由 ChatGPT 4.1 翻译