D1. Рассадка в кинотеатре (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие состоит в том, что в этой версии $$$n = 1$$$.

В кинотеатре места могут быть представлены как таблица из $$$n$$$ рядов и $$$m$$$ столбцов. Ряды нумеруются целыми числами от $$$1$$$ до $$$n$$$. Места в каждом ряду нумеруются последовательными целыми числами слева направо: в $$$k$$$-м ряду от $$$m (k - 1) + 1$$$ до $$$m k$$$ для всех рядов $$$1 \le k \le n$$$.

$$$1$$$$$$2$$$$$$\cdots$$$$$$m - 1$$$$$$m$$$
$$$m + 1$$$$$$m + 2$$$$$$\cdots$$$$$$2 m - 1$$$$$$2 m$$$
$$$2m + 1$$$$$$2m + 2$$$$$$\cdots$$$$$$3 m - 1$$$$$$3 m$$$
$$$\vdots$$$$$$\vdots$$$$$$\ddots$$$$$$\vdots$$$$$$\vdots$$$
$$$m (n - 1) + 1$$$$$$m (n - 1) + 2$$$$$$\cdots$$$$$$n m - 1$$$$$$n m$$$
Таблица с номерами мест

Есть $$$nm$$$ людей, которые хотят прийти в кинотеатр, чтобы посмотреть новый фильм. Они пронумерованы целыми числами от $$$1$$$ до $$$nm$$$. Вы должны задать ровно одно место для каждого человека.

Известно, что в этом кинотеатре чем меньше номер места, тем лучше виден экран. У $$$i$$$-го человека уровень зрения $$$a_i$$$. Обозначим за $$$s_i$$$ номер места $$$i$$$-го человека. Необходимо выдать место лучше тем, у кого зрение хуже, то есть для любых двух людей $$$i$$$, $$$j$$$ таких, что $$$a_i < a_j$$$, должно выполняться условие $$$s_i < s_j$$$.

После того, как вы определите места всем людям, они начнут их занимать. В порядке от $$$1$$$ до $$$nm$$$ каждый человек входит в зал и садится на своё место. Чтобы сесть, человек подходит к своему ряду и начинает двигаться от первого места в ряду к своему слева направо. Во время того, как человек будет занимать свое место, какие-то места будут свободны, какие-то будут заняты теми людьми, которые уже вошли в зал. Неудобство человека равно количеству занятых мест, мимо которых он прошёл, пока занимал своё место.

Рассмотрим пример: $$$m = 5$$$, человеку определено место $$$4$$$ в первом ряду, причём места $$$1$$$, $$$3$$$, $$$5$$$ в первом ряду уже заняты, а места $$$2$$$ и $$$4$$$ свободны. Неудобство этого человека будет равно $$$2$$$, потому что он пройдет мимо двух занятых мест: $$$1$$$ и $$$3$$$.

Найдите минимальное общее неудобство (сумму неудобств всех людей), которое можно получить, задав места для всех людей (при этом все условия должны быть выполнены).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$n = 1$$$, $$$1 \le m \le 300$$$) — количество рядов и мест в каждом ряду кинотеатра соответственно.

Следующая строка содержит $$$n \cdot m$$$ целых чисел $$$a_1, a_2, \ldots, a_{n \cdot m}$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — уровень зрения $$$i$$$-го человека.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$10^5$$$.

Выходные данные

Для каждого набора выходных данных выведите единственное целое число — минимальное общее неудобство, которое можно получить.

Пример
Входные данные
4
1 3
1 2 3
1 5
2 1 5 3 3
1 2
2 1
1 6
2 3 2 1 1 1
Выходные данные
3
6
0
1
Примечание

В первом наборе входных данных существует единственный способ определить людям места, потому что все уровни зрения различны. Первый человек занимает первое место, второй человек занимает второе место, третий человек занимает третье место. Неудобство первого человека равно $$$0$$$, второго — $$$1$$$, а третьего — $$$2$$$. Общее неудобство равно $$$0 + 1 + 2 = 3$$$.

Во втором наборе входных данных люди должны занять следующие места: $$$s_1 = 2$$$, $$$s_2 = 1$$$, $$$s_3 = 5$$$, $$$s_4 = 4$$$, $$$s_5 = 3$$$. Общее неудобство будет равно $$$6$$$.