该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在星际探险过程中，探险队长酥酥发现了一条神秘的星际航道，这条航道由 $n$ 个星系组成，每个星系都有其独特的风险值。第 $i$ 个星系的风险值为 $a_i$。酥酥认为一个航段内的星系风险应该是逐渐增加的，以保证航道的平稳过渡和队伍的安全。因此，对于一段连续的星系序列 $[l, r]$，她将这段序列的『风险不协调度』定义为该序列内逆序对的数量。

一个序列 $[l, r]$ 的逆序对数被定义为满足 $l \leq i < j \leq r$ 且 $a_i > a_j$ 的数对 $(i, j)$ 的个数。

酥酥希望将这条星际航道划分成至多 $k$ 个航段，确保每个星系至少位于一个航段内，以使得风险不协调度最高的航段的风险不协调度尽可能低。

形式化的讲，需要划分出 $t \leq k$ 个序列 $[l_1, r_1], [l_2, r_2], \dots, [l_t, r_t]$，满足：

• $l_1 = 1$，$r_t = n$。
• 对于所有的 $1 \leq i < t$，有 $r_i + 1= l_{i + 1}$。
• 对于所有的 $1 \leq i \leq t$，有 $l_i \leq r_i$。

定义 $f(l, r)$ 为序列 $[l, r]$ 的风险不协调度，求最小化 $\max\limits_{i = 1}^t f(l_i, r_i)$ 的值。

输入格式

本题单个测试点内有多组测试数据。第一行是一个正整数 $T$，表示数据组数。对于每组数据：

第一行是两个整数 $n,k$（$1 \leq k \leq n \leq 10^5$），表示星际航道中的星系数和最多的航段数。 第二行有 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示每个星系的风险值。

数据保证单个测试点内的 $n$ 之和不超过 $10^5$。

输出格式

对每组数据，输出一行一个整数，表示答案。

2
8 2
4 2 3 6 7 1 8 5
5 2
1 3 2 5 4

2
1