Sequence Sorting

有n个数的序列，每次操作可以选择一种数，将他们全部移到开头或结尾： - 1,5,2,1,3,2 -> 1,1,5,2,3,2（选1） - 1,5,2,1,3,2 -> 5,2,3,2,1,1（选1） 问最少需要多少次操作，才能使序列变为非递减序列。

You are given a sequence $ a_1, a_2, \dots, a_n $ , consisting of integers. You can apply the following operation to this sequence: choose some integer $ x $ and move all elements equal to $ x $ either to the beginning, or to the end of $ a $ . Note that you have to move all these elements in one direction in one operation. For example, if $ a = [2, 1, 3, 1, 1, 3, 2] $ , you can get the following sequences in one operation (for convenience, denote elements equal to $ x $ as $ x $ -elements): - $ [1, 1, 1, 2, 3, 3, 2] $ if you move all $ 1 $ -elements to the beginning; - $ [2, 3, 3, 2, 1, 1, 1] $ if you move all $ 1 $ -elements to the end; - $ [2, 2, 1, 3, 1, 1, 3] $ if you move all $ 2 $ -elements to the beginning; - $ [1, 3, 1, 1, 3, 2, 2] $ if you move all $ 2 $ -elements to the end; - $ [3, 3, 2, 1, 1, 1, 2] $ if you move all $ 3 $ -elements to the beginning; - $ [2, 1, 1, 1, 2, 3, 3] $ if you move all $ 3 $ -elements to the end; You have to determine the minimum number of such operations so that the sequence $ a $ becomes sorted in non-descending order. Non-descending order means that for all $ i $ from $ 2 $ to $ n $ , the condition $ a_{i-1} \le a_i $ is satisfied. Note that you have to answer $ q $ independent queries.

The first line contains one integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of the queries. Each query is represented by two consecutive lines. The first line of each query contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of elements. The second line of each query contains $ n $ integers $ a_1, a_2, \dots , a_n $ ( $ 1 \le a_i \le n $ ) — the elements. It is guaranteed that the sum of all $ n $ does not exceed $ 3 \cdot 10^5 $ .

For each query print one integer — the minimum number of operation for sorting sequence $ a $ in non-descending order.

3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7

2
0
1

In the first query, you can move all $ 1 $ -elements to the beginning (after that sequence turn into $ [1, 1, 1, 3, 6, 6, 3] $ ) and then move all $ 6 $ -elements to the end. In the second query, the sequence is sorted initially, so the answer is zero. In the third query, you have to move all $ 2 $ -elements to the beginning.