有一天,你想读点东西,所以你去书架拿了一本书。但当你看到书架有多乱时,你决定先把它清理干净。
书架上有 $$$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]$$$。