404529: GYM101532 I The Crazy Jumper

Universal Studios Theme Parks announced a new game named The Crazy Jumper, that is targeted problem solving fans.

In this game, there are n large boxes numbered from 1 to n from left to right, such that the i^th box (1 < i ≤ n) is located to the right of the (i - 1)^th box. Each box has a color, such that c_i is the color of the i^th box.

The goal of the game is to reach the n^th box starting from the 1^st box, by jumping between the boxes. The player can do one of the following jumps:

1. Jump one box to the right.
2. If the player stands at a box of color x, he/she can jump to the closest box of color x that is to the right of him, if such box exist.

Ziad will be the first one to play the game, but he is not sure whether the game is amusing or not, so he wants to finish it with the minimum number of jumps. Can you help Ziad by telling him what is the minimum number of required jumps to reach the n^th box stating from the 1^st box?

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 × 10⁵), where n is the number of the boxes in the game.

The second line of each test case contains n integers c₁, c₂, ..., c_n (1 ≤ c_i ≤ 2 × 10⁵), where c_i is the color of the i^th box.

For each test case, print a single line containing the minimum number of required jumps to reach the n^th box starting from the 1^st box.

3
6
9 2 4 7 1 5
5
1 2 1 1 4
6
1 2 3 1 3 2

5
3
2

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.