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