F1. Велосипедисты (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Разница между версиями заключается в том, что в этой версии $$$1\le n\le 5\cdot 10^3$$$ и вам не нужно выводить ответ для каждого префикса. Вы можете совершать взломы только в том случае, если решены все версии этой задачи.

Лео работает программистом в центре города, а его возлюбленная преподает в средней школе на окраине. Каждые выходные Лео ездит на своем велосипеде в пригород, чтобы провести приятные выходные с любимой.

Сейчас на этой дороге перед Лео едет $$$n$$$ велосипедистов. Они пронумерованы $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$ от передней части к задней. Изначально Лео находится позади $$$n$$$-го велосипедиста. У $$$i$$$-го велосипедиста есть значение ловкости $$$a_i$$$.

Лео хочет обогнать $$$1$$$-го велосипедиста. Лео может выполнять следующие действия столько раз, сколько захочет:

  • Предположим, что первым перед Лео находится велосипедист $$$i$$$, тогда он может обогнать велосипедиста $$$i$$$ за стоимость $$$a_i$$$. Это ставит его позади велосипедиста $$$i - 1$$$.
  • Используя свои суперспособности, обменять $$$a_i$$$ и $$$a_j$$$ ($$$1\le i \lt j\le n$$$) за стоимость $$$(j - i)$$$.

Лео хочет узнать минимальную стоимость, чтобы оказаться перед $$$1$$$-м велосипедистом. В этой версии вам нужно вывести ответ только для всего массива, т.е. $$$[a_1, a_2, \ldots, a_n]$$$.

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

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

Первая строка каждого набора входных данных содержит целое положительное число $$$n$$$ ($$$1 \leq n \leq 5\cdot 10^3$$$), представляющее количество велосипедистов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

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

Для каждого набора входных данных выведите одно целое число, представляющее минимальную стоимость для Лео, чтобы перейти с позиции позади $$$n$$$-го велосипедиста до позиции перед $$$1$$$-м велосипедистом.

Пример
Входные данные
4
3
1 2 4
4
1 1 1 1
2
1 2
4
4 1 3 2
Выходные данные
7
4
3
8
Примечание

В первом наборе входных данных одним из возможных способов из позиции позади $$$n$$$-го велосипедиста попасть на позицию перед $$$1$$$-м велосипедистом может быть:

  • Лео меняет местами $$$a_2$$$ $$$(i=2)$$$ и $$$a_3$$$ $$$(j=3)$$$, тогда массив становится $$$[1,4,2]$$$, это стоит $$$j-i=3-2=1$$$.
  • Лео переходит на позицию позади $$$2$$$-го велосипедиста с позиции позади $$$3$$$-го велосипедиста; это стоит $$$a_3=2$$$.
  • Лео меняет местами $$$a_1$$$ $$$(i=1)$$$ и $$$a_2$$$ $$$(j=2)$$$, тогда массив становится $$$[4,1,2]$$$, это стоит $$$j-i=2-1=1$$$.
  • Лео переходит на позицию позади $$$1$$$-го велосипедиста с позиции позади $$$2$$$-го велосипедиста; это стоит $$$a_2=1$$$.
  • Лео меняет местами $$$a_1$$$ $$$(i=1)$$$ и $$$a_2$$$ $$$(j=2)$$$, тогда массив становится $$$[1,4,2]$$$, это стоит $$$j-i=2-1=1$$$.
  • Лео обгоняет $$$1$$$-го велосипедиста; это стоит $$$a_1=1$$$.

Таким образом, общая стоимость составляет $$$1+2+1+1+1+1=7$$$. Можно доказать, что $$$7$$$ является минимальной стоимостью.

Во втором наборе входных данных, чтобы из позиции позади $$$n$$$-го велосипедиста попасть на позицию перед $$$1$$$-м велосипедистом, Лео не нужно менять местами значения ловкости. Общая стоимость составляет $$$1+1+1+1=4$$$.