Дан массив $$$a_1, a_2, \ldots, a_n$$$. За одну операцию вы можете выбрать пару индексов $$$i, j$$$ такую, что $$$1 \le i \lt j \le n$$$, $$$a_i \gt a_j$$$, и удалить элемент под номером $$$j$$$ из массива. После чего размер массива уменьшится на $$$1$$$, а относительный порядок элементов не поменяется.
Определите, какое максимальное число операций можно совершить над массивом, если применять их оптимально.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$) — размер исходного массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).
Для каждого набора входных данных выведите максимальное количество операций, которое вы можете совершить над данным массивом.
533 2 131 2 333 3 353 1 4 5 211
20020
В первом примере мы можем выбрать сначала пару $$$i = 2$$$, $$$j = 3$$$ со значениями $$$a_2 = 2$$$, $$$a_3 = 1$$$ и удалить $$$a_3$$$. Полученный массив будет иметь вид $$$a = [3, 2]$$$. После чего удалить второй элемент, выбрав пару $$$i = 1$$$, $$$j = 2$$$. Итоговое число операций — $$$2$$$.
Во втором, третьем и пятом примерах нельзя сделать ни одной операции, так как нет ни одной подходящей пары.
В четвёртом примере можно удалить второй и пятый элементы. Можно показать, что это оптимальный ответ и нет решения, удаляющего большее количество элементов.
| Codeforces Round 1070 (Div. 2) |
|---|
| Закончено |
