Codeforces Round 925 (Div. 3) |
---|
Закончено |
У вас есть массив $$$a$$$ из $$$n$$$ целых чисел.
Вы можете не более одного раза применить следующую операцию: выбрать три целых числа $$$i$$$, $$$j$$$, $$$x$$$ ($$$1 \le i \le j \le n$$$) и присвоить всем элементам массива с индексами от $$$i$$$ до $$$j$$$ значение $$$x$$$. Цена данной операции зависит от выбранных индексов и равна $$$(j - i + 1)$$$ бурлей.
Например, массив равен $$$[1, 2, 3, 4, 5, 1]$$$. Если мы выберем $$$i = 2, j = 4, x = 8$$$, то после применения данной операции массив будет равен $$$[1, 8, 8, 8, 5, 1]$$$.
Какое наименьшее количество бурлей нужно потратить, чтобы сделать все элементы массива равными?
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка описания каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$) — размер массива.
Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество бурлей, которое придётся потратить, чтобы сделать все элементы массива равными. Можно показать, что это всегда можно сделать.
861 2 3 4 5 171 1 1 1 1 1 188 8 8 1 2 8 8 81121 231 2 374 3 2 7 1 1 399 9 2 9 2 5 5 5 3
4 0 2 0 1 2 6 7
Название |
---|