Partitioning Song Segments Minimizing Worst Inversion Count

You are given a song consisting of n notes, each with an integer difficulty. The difficulty of the i-th note is \(a_i\). The inversion count of an interval \([l, r]\) is defined as the number of pairs \((i, j)\) such that \(l \le i a_j\).

Fusu believes that the difficulty of a segment of the song should escalate as much as possible. Therefore, she wants to partition the song into at most k contiguous segments in such a way that every note is included in exactly one segment, and the maximum inversion count among all segments is minimized. Formally, you need to choose \(t \le k\) segments \([l_1, r_1], [l_2, r_2], \dots, [l_t, r_t]\) such that:

• \(l_1 = 1\) and \(r_t = n\).
• For every \(1 \le i < t\), \(r_i + 1 = l_{i+1}\).
• For every \(1 \le i \le t\), \(l_i \le r_i\).

Let \(f(l, r)\) denote the inversion count of the interval \([l, r]\). Your task is to partition the song so that the value \(\max_{1 \le i \le t} f(l_i, r_i)\) is as small as possible.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10^5\), \(1 \le k \le n\)) — the number of notes in the song and the maximum number of segments allowed.

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) representing the difficulty values of the notes.

outputFormat

Output a single integer, the minimized maximum inversion count among all segments after an optimal partition.

sample

5 3
3 1 2 5 4

2