← 返回题目列表

Codeforces · 1481/E

E. 整理书籍

中文机器翻译题面 查看原题

有一天,你想读点东西,所以你去书架拿了一本书。但当你看到书架有多乱时,你决定先把它清理干净。

书架上有 $$$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

5
1 2 2 1 3

输出 #1

2

输入 #2

5
1 2 2 1 1

输出 #2

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]$$$。