| Codeforces Round 699 (Div. 2) |
|---|
| Закончено |
Однажды вы решили почитать какую-нибудь книгу на книжной полке в соседней комнате. Но когда вы увидели, какой беспорядок творится на полке, то захотели сначала на ней разобраться.
У вас есть $$$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$$$) — цвета книг.
Выведите наименьшее количество операций, чтобы сделать полку красивой.
5 1 2 2 1 3
2
5 1 2 2 1 1
1
В первом примере у нас есть полка с книгами $$$[1, 2, 2, 1, 3]$$$ и мы можем, например:
- взять книгу на позиции $$$4$$$ и переместить ее в правый конец: мы получим $$$[1, 2, 2, 3, 1]$$$;
- взять книгу на позиции $$$1$$$ и переместить ее в правый конец: мы получим $$$[2, 2, 3, 1, 1]$$$.
Во втором примере, мы можем переместить первую книгу в конец полки и получить $$$[2,2,1,1,1]$$$.
