Задача . C. Изменение последовательности

Вам задана последовательность \(a\), изначально состоящая из \(n\) целых чисел.

Вы хотите изменить эту последовательность таким образом, чтобы все элементы в ней были равны между собой (то есть чтобы она состояла из какого-то количества вхождений одного элемента).

Чтобы это сделать, вы выбираете какое-то целое число \(x\), которое встречается в \(a\) хотя бы раз, и затем совершаете следующую операцию любое количество раз (возможно, нулевое): выбираете какой-то отрезок последовательности \([l, r]\) и удаляете его. Но есть одно исключение: вы не можете выбирать отрезки, которые содержат \(x\). Более формально, вы выбираете какую-то такую последовательную подпоследовательность \([a_l, a_{l + 1}, \dots, a_r]\), что \(a_i \ne x\) для \(l \le i \le r\), и удаляете ее. После удаления индексация элементов справа от удаленного отрезка меняется: элемент, который был \((r+1)\)-м, становится \(l\)-м, элемент, который был \((r+2)\)-м, становится \((l+1)\)-м, и так далее (то есть последовательность просто схлопывается).

Заметьте, что вы не можете изменять \(x\) после того, выбрали его.

Например, пусть \(n = 6\), \(a = [1, 3, 2, 4, 1, 2]\). Тогда одним из способов изменить ее за две операции является выбрать \(x = 1\), а затем:

1. выбрать \(l = 2\), \(r = 4\), после чего получится последовательность \(a = [1, 1, 2]\);
2. выбрать \(l = 3\), \(r = 3\), после чего получится последовательность \(a = [1, 1]\).

Заметьте, что выбор \(x\) не является операцией. Также заметьте, что вы не можете удалять никакое вхождение \(x\).

Ваша задача — найти минимальное количество операций, необходимое для того, чтобы изменить последовательность так, как описано выше.

Вам необходимо ответить на \(t\) независимых наборов тестовых данных.