A6908. 舞萌基本练习

Welcome24ever 在游玩舞萌 dx 的过程中，发现一首歌可以分成不超过 $k$ 段分别进行练习。

具体来说，这首歌共有 $n$ 个音符，每个音符有一个难度值。第 $i$ 个音符的难度值为 $a_i$。Welcome24ever 觉得一段歌曲的音符的难度应该是尽可能变难的。因此对于音符序列的一个区间 $[l, r]$，她认为这段区间的「不优美度」是这段区间的**逆序对**数。

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

Welcome24ever 希望把这首歌划分成不超过 $k$ 个子段，满足每个音符都至少属于一个子段，使得「不优美度最大的段」的不优美度尽可能小。

形式化地，你需要划分出 $t \le k$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_t, r_t]$，满足：

- $l_1 = 1$，$r_t = n$。
- 对 $1 \le i < t$，$r_i + 1 = l_{i+1}$。
- 对 $1 \le i \le t$，$l_i \le r_i$。

定义 $f(l, r)$ 表示区间 $[l, r]$ 的不优美度，目标是最小化：
$\max\limits_{i=1}^{t} f(l_i, r_i)$。

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

第一行是两个整数 $n,k$（$1 \le k \le n \le 10^5$），表示歌曲的音符数和最多的划分段数。
第二行有 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$），表示每个音符的难度。

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

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

## 样例解释

### 第 $1$ 组
$n=5,k=2$，$a=[1,3,2,5,4]$。

例如把它分成两段：
- 第 $1$ 段 $[1,3]$：$[1,3,2]$，逆序对是 $(2,3)$（因为 $a_2=3>a_3=2$），所以 $f(1,3)=1$。
- 第 $2$ 段 $[4,5]$：$[5,4]$，逆序对是 $(4,5)$（因为 $a_4=5>a_5=4$），所以 $f(4,5)=1$。

此时 $\max(f(1,3),f(4,5))=\max(1,1)=1$，可以达到答案 $1$。

### 第 $2$ 组
$n=8,k=2$，$a=[4,2,3,6,7,1,8,5]$。
通过合适地分成两段，可以让「不优美度最大的段」的最小可能值为 $2$，所以答案是 $2$。