Sorting Books
Contest: Codeforces Round 699 (Div. 2)
Difficulty rating: 2500
Tags: data structures, dp, greedy

One day you wanted to read something, so you went to your bookshelf to grab some book. But when you saw how messy the bookshelf was you decided to clean it up first.

There are $$$n$$$ books standing in a row on the shelf, the $$$i$$$-th book has color $$$a_i$$$.

You'd like to rearrange the books to make the shelf look beautiful. The shelf is considered beautiful if all books of the same color are next to each other.

In one operation you can take one book from any position on the shelf and move it to the right end of the shelf.

What is the minimum number of operations you need to make the shelf beautiful?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of books.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the book colors.

Output format:
Output the minimum number of operations to make the shelf beautiful.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, we have the bookshelf $$$[1, 2, 2, 1, 3]$$$ and can, for example:

1. take a book on position $$$4$$$ and move to the right end: we'll get $$$[1, 2, 2, 3, 1]$$$;
2. take a book on position $$$1$$$ and move to the right end: we'll get $$$[2, 2, 3, 1, 1]$$$.

In the second example, we can move the first book to the end of the bookshelf and get $$$[2,2,1,1,1]$$$.

Example input:
5
1 2 2 1 3

Example output:
2

Example input:
5
1 2 2 1 1

Example output:
1

Editorial:
Lets try to solve the opposite version of the problem where you want to find the maximum number of books that will stay unmoved, so we will choose number of books that will stay unmoved and then move the rest in a way that will make the shelf beautiful.
To do that lets first for each color $$$c$$$ find the leftmost and rightmost occurrence $$$l_c$$$ and $$$r_c$$$ and the frequency of this color $$$f_c$$$.Then we will use $$$dp_i$$$ which will find for each $$$i$$$ the maximum number of books that we can leave unmoved in the suffix $$$[i,n]$$$.
We will go from right to left and for each index $$$i$$$ the $$$dp$$$ will work as follow :
• If $$$i = l_{a_i}$$$, we leave all occurrences of color $$$a_i$$$ unmoved and move everything in between the first and last occurrence of color $$$a_i$$$, so between $$$l_{a_i}$$$ and $$$r_{a_i}$$$ only books with color $$$a_i$$$ will stay unmoved, we can see that this will be only true if we are at the first occurrence of color $$$a_i$$$ (when $$$i = l_{a_i}$$$ because we want to cover the segment $$$[l_{a_i} , r_{a_i}]$$$), as a result $$$dp_i = f_{a_i} + dp_{r_{a_i} + 1}$$$.
• If $$$i \ne l_{a_i}$$$, we can keep all books with color $$$a_i$$$ in range $$$[i,n]$$$ unmoved and move everything else, as a result $$$dp_i = cf_{a_i}$$$ where $$$cf_{a_i}$$$ is the number of books with color $$$a_i$$$ in range $$$[i,n]$$$ (we can update this array as we move) (note that here we move all books even those after $$$r_{a_i}$$$).
• In either cases we can move the book $$$a_i$$$ and get $$$dp_i = dp_{i+1}$$$.
The answer will be $$$n - dp_1$$$ and the time is $$$O(n)$$$.