Codeforces Round 913 (Div. 3) |
---|
Закончено |
Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Вы можете выполнять два типа операций с этим массивом:
Ваша задача — отсортировать массив в порядке неубывания с использованием минимального количества операций или определить, что это невозможно.
Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Описание наборов входных данных следует далее.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n \le 10^5$$$) — размер массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите число $$$k$$$ — минимальное количество операций, необходимых для сортировки массива. Если невозможно отсортировать массив с помощью этих операций, выведите $$$-1$$$.
1153 2 1 5 451 1 2 1 143 7 10 551 2 3 4 525 133 4 154 1 3 4 435 1 142 5 5 452 2 1 1 225 5
3 2 -1 0 1 1 3 1 2 2 0
В первом наборе входных данных примера, чтобы отсортировать массив [$$$3, 2, 1, 5, 4$$$] нужно выполнить $$$3$$$ операции:
В третьем наборе входных данных примера можно показать, что массив невозможно отсортировать с помощью данных операций.
В седьмом наборе входных данных примера, чтобы отсортировать массив [$$$4, 1, 3, 4, 4$$$] нужно выполнить $$$3$$$ операции:
Название |
---|