Вам дан массив \(a_1, a_2, \dots, a_n\), где каждый элемент является целым числом от \(1\) до \(x\).
Вы можете выполнять следующую операцию любое количество раз:
- выберите три целых числа \(l\), \(r\) и \(k\) таких, что \(1 \le l \le r \le n\), \(1 \le k \le x\) и каждый элемент \(a_i\), для которого \(l \le i \le r\), отличается от \(k\). Затем для каждого \(i \in [l, r]\) замените \(a_i\) на \(k\).
Другими словами, вы выбираете подотрезок массива и целое число от \(1\) до \(x\), которое не встречается в этом подотрезке, и заменяете каждый элемент в подотрезке на это выбранное число.
Ваша цель — сделать все элементы в массиве равными. Какое минимальное количество операций вам нужно выполнить?
Выходные данные
Для каждого теста выведите одно целое число — минимальное количество операций, которые вам нужно выполнить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2
1 2 1
6 3
1 2 3 1 2 3
12 3
3 1 3 1 2 1 1 2 3 1 1 3
|
1
2
2
|