题目描述

账本上一共有 $n$ 条记录，按时间顺序排列，第 $i$ 条记录的类型为 $a_i$。

审计员需要把账本切成恰好 $k$ 段连续区间。每一段至少包含 $L$ 条记录，至多包含任意多条记录。一段记录的"混乱度"定义为这段内记录类型的最大值与最小值之差，即 $\max\{a_i\}-\min\{a_i\}$。

总混乱度是各段的混乱度之和。审计员希望总混乱度尽可能小，以便后续核对；请你求出最小的总混乱度。输入保证至少存在一种合法的划分方式。

输入数据保证 $k \times L \le n$，因此一定可以切出恰好 $k$ 段、且每段都不少于 $L$ 条记录的划分；不满足长度下限的切法一律视为不合法。

审计员可以从任意位置下刀，但每一刀都必须落在两条相邻记录之间。

同一条记录不能同时属于两段，所有记录都必须恰好属于其中的某一段。划分必须保持记录原有的先后顺序。

输入的第二行恰好包含 $n$ 个整数，相邻两个整数之间用一个空格分隔；账本中的记录按照时间先后排列，位置从 $1$ 开始编号。

输入的第一行包含三个正整数 $n,k,L$，相邻两个整数之间用一个空格分隔。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,k,L$。

输入的第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，依次表示每条记录的类型。

输入保证每条记录的类型编号都是不超过 $10^{9}$ 的正整数，且 $k\times L\le n$。

输出文件仅包含一行，行末不要有多余的空格。

输出格式

输出到标准输出中。

输出一行一个整数，表示最小的总混乱度。

样例 1 输入

7 2 1
1 2 3 1 2 3 1

样例 1 输出

2

样例 1 解释

把账本切成 $[1,1]$ 与 $[2,7]$：第一段只有一个数，混乱度为 $0$；第二段包含 $2,3,1,2,3,1$，最大值为 $3$、最小值为 $1$，混乱度为 $2$。总混乱度为 $2$。

切成 $[1,6]$ 与 $[7,7]$ 同样得到 $2$。可以证明不存在总混乱度小于 $2$ 的方案。

样例 2 输入

5 3 1
5 5 5 5 5

样例 2 输出

0

样例 2 解释

所有记录类型相同，任意一段的混乱度都是 $0$。

样例 3

见选手目录下的 ledger/ledger3.in 与 ledger/ledger3.ans。

该样例满足测试点 $3\sim 5$ 的约束条件。

样例 4

见选手目录下的 ledger/ledger4.in 与 ledger/ledger4.ans。

该样例满足测试点 $6\sim 8$ 的约束条件。

样例 5

见选手目录下的 ledger/ledger5.in 与 ledger/ledger5.ans。

该样例满足测试点 $22\sim 25$ 的约束条件。

数据范围

对于所有测试数据，保证：

• $1\le k\le n\le 2\times 10^{5}$；
• $1\le L\le n$，且 $k\times L\le n$；
• 对于所有 $1\le i\le n$，均有 $1\le a_i\le 10^{9}$。

特殊性质 A：所有 $a_i$ 相同。

特殊性质 B：$k=1$。

特殊性质 C：$k=n$。

特殊性质 D：$k=2$。