Однажды вы решили почитать какую-нибудь книгу на книжной полке в соседней комнате. Но когда вы увидели, какой беспорядок творится на полке, то захотели сначала на ней разобраться.
У вас есть \(n\) книг, стоящих в ряд на полке, обложка \(i\)-й книги имеет цвет \(a_i\).
Вы хотите переставить книги так, чтобы сделать полку красивой. Полка считается красивой, если все книги одного цвета стоят подряд.
За одну операцию, вы можете взять одну любую книгу на полке и переставить ее в правый конец полки.
Какое наименьшее количество операций вам понадобится, чтобы сделать полку красивой?
Выходные данные
Выведите наименьшее количество операций, чтобы сделать полку красивой.
Примечание
В первом примере у нас есть полка с книгами \([1, 2, 2, 1, 3]\) и мы можем, например:
- взять книгу на позиции \(4\) и переместить ее в правый конец: мы получим \([1, 2, 2, 3, 1]\);
- взять книгу на позиции \(1\) и переместить ее в правый конец: мы получим \([2, 2, 3, 1, 1]\).
Во втором примере, мы можем переместить первую книгу в конец полки и получить \([2,2,1,1,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 2 1 3
|
2
|
|
2
|
5
1 2 2 1 1
|
1
|