Problem Description

While playing MaiMai dx, Fusu found that a song can be split into at most $k$ segments for separate practice.

Specifically, the song has $n$ notes, and each note has a difficulty value. The difficulty of the $i$-th note is $a_i$. Fusu thinks that the notes in a segment should become as difficult as possible. Therefore, for an interval $[l, r]$ of the note sequence, she defines the “non-beauty” of this interval as the number of inversion pairs in this interval.

The number of inversion pairs in an interval $[l, r]$ is defined as the number of pairs $(i, j)$ such that $l \leq i < j \leq r$ and $a_i > a_j$.

Fusu wants to partition the song into at most $k$ subsegments, so that every note belongs to at least one subsegment, and the maximum non-beauty among all segments is as small as possible.

Formally, you need to split it into $t \leq k$ intervals $[l_1, r_1], [l_2, r_2], \dots [l_t, r_t]$, satisfying:

• $l_1 = 1$, $r_t = n$.
• For $1 \leq i < t$, $r_i + 1 = l_{i + 1}$.
• For $1 \leq i \leq t$, $l_i \leq r_i$.

Let $f(l, r)$ denote the non-beauty of interval $[l, r]$. Minimize $\max\limits_{i = 1}^t f(l_i, r_i)$.

Input Format

This problem contains multiple test cases within a single test file. The first line contains a positive integer $T$, the number of test cases. For each test case:

The first line contains two integers $n, k$ ($1 \leq k \leq n \leq 10^5$), representing the number of notes in the song and the maximum number of segments.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$), representing the difficulty of each note.

It is guaranteed that the sum of $n$ over all test cases within a single test file does not exceed $10^5$.

Output Format

For each test case, output one line with one integer, representing the answer.

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

1
2

Hint

Translated by ChatGPT 5