这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$1\le n\le 5\cdot 10^3$$$ 并且不需要输出每个前缀的答案。只有解决了该问题的所有版本,您才能破解。
Leo在市中心做程序员,他的爱人在郊区的一所高中教书。每个周末,Leo都会骑着自行车去郊区,和爱人一起度过一个美好的周末。
现在这条路上有 $$$n$$$ 骑自行车的人在 Leo 前面骑行。它们从前到后编号为 $$$1$$$、$$$2$$$、$$$\ldots$$$、$$$n$$$。最初,Leo 位于第 $$$n$$$ 位自行车手的后面。第 $$$i$$$ 位自行车手的敏捷度值为 $$$a_i$$$。
Leo 想领先于 $$$1$$$-st 骑自行车的人。 Leo 可以根据需要多次执行以下操作:
- 假设Leo前面的第一个人是骑自行车的人$$$i$$$,他可以走到骑自行车的人$$$i$$$前面,成本为$$$a_i$$$。这使他落后于自行车手 $$$i - 1$$$。
- 使用他的超能力,交换 $$$a_i$$$ 和 $$$a_j$$$ ($$$1\le i \lt j\le n$$$),成本为 $$$(j - i)$$$。
Leo 想知道排在 $$$1$$$-st 骑车人前面的最低成本。这里你只需要打印整个数组的答案,即$$$[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$$$。
输出
对于每个测试用例,打印一个整数,表示 Leo 从第 $$$n$$$ 位骑车人后面走到第 $$$1$$$ 位骑车人前面的最小成本。
示例
输入复制
431 2 441 1 1 121 244 1 3 2
输出复制
7 4 3 8
注意
在第一个测试用例中,从第 $$$n$$$ 位骑车人后面的位置移动到第 $$$1$$$ 位骑车人前面的位置的一种可能方法是:
- Leo 交换 $$$a_2$$$ $$$(i=2)$$$ 和 $$$a_3$$$ $$$(j=3)$$$,则数组变为 $$$[1,4,2]$$$;它的成本为$$$j-i=3-2=1$$$。
- Leo 位于第 $$$3$$$-rd 骑车人后面,并移动到第 $$$2$$$-nd 骑车人后面;花费$$$a_3=2$$$。
- Leo 交换 $$$a_1$$$ $$$(i=1)$$$ 和 $$$a_2$$$ $$$(j=2)$$$,则数组变为 $$$[4,1,2]$$$;它的成本为$$$j-i=2-1=1$$$。
- Leo 位于第 $$$2$$$-nd 骑车人后面,并移动到第 $$$1$$$-st 骑车人后面;成本为$$$a_2=1$$$。
- Leo 交换 $$$a_1$$$ $$$(i=1)$$$ 和 $$$a_2$$$ $$$(j=2)$$$,则数组变为 $$$[1,4,2]$$$;它的成本为$$$j-i=2-1=1$$$。
- Leo 领先于 $$$1$$$-st 自行车手;成本为$$$a_1=1$$$。
因此总成本为$$$1+2+1+1+1+1=7$$$。可以证明$$$7$$$是最小成本。
在第二个测试用例中,为了从第 $$$n$$$ 位自行车手后面的位置移动到第 $$$1$$$ 位自行车手的前面,Leo 不应交换任何人的敏捷性值。总成本为$$$1+1+1+1=4$$$。