Это сложная версия задачи. В этой версии в заданном массиве могут встречаться одинаковые числа и ограничения на \(n\) больше, чем в простой версии задачи.
Вам дан массив \(a\) из \(n\) целых чисел (в массиве могут быть одинаковые элементы). Вы можете производить над элементами массива следующие операции:
- выбрать любой индекс \(i\) (\(1 \le i \le n\)) и переместить элемент \(a[i]\) в начало массива;
- выбрать любой индекс \(i\) (\(1 \le i \le n\)) и переместить элемент \(a[i]\) в конец массива.
Например, если \(n = 5\), \(a = [4, 7, 2, 2, 9]\), то можно применить следующую последовательность операций:
- После применения операции первого типа ко второму элементу массив \(a\) станет равным \([7, 4, 2, 2, 9]\);
- После применения операции второго типа ко второму элементу массив \(a\) станет равным \([7, 2, 2, 9, 4]\).
Вы можете проводить операции любого типа произвольное количество раз в любом порядке.
Найдите минимальное суммарное количество операций первого и второго типа, которые сделают массив \(a\) отсортированным по неубыванию. Иными словами, сколько минимум операций надо применить, чтобы массив удовлетворял неравенствам \(a[1] \le a[2] \le \ldots \le a[n]\)?
Выходные данные
Для каждого набора тестовых данных выведите одно целое число — минимальное суммарное количество операций первого и второго типа, которые сделают массив отсортированным по неубыванию.
Примечание
В первом тестовом наборе нужно переместить две двойки в начало массива. Следовательно, искомая последовательность операций может иметь вид: \([4, 7, 2, 2, 9] \rightarrow [2, 4, 7, 2, 9] \rightarrow [2, 2, 4, 7, 9]\).
Во втором тестовом наборе нужно переместить единицу в начало массива, а восьмерку — в конец. Искомая последовательность операций имеет вид: \([3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]\).
В третьем тестовом наборе массив уже отсортирован.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
5
4 7 2 2 9
5
3 5 8 1 7
5
1 2 2 4 5
2
0 1
3
0 1 0
4
0 1 0 0
4
0 1 0 1
4
0 1 0 2
20
16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9
|
2
2
0
0
1
1
1
1
16
|