#BT07. 交出你的切法

交出你的切法

交出你的切法

有 nn 个非负整数 a1,…,ana_1,\ldots,a_n。请把它们分成恰好 KK 个非空连续段,使这些段的和的最大值尽可能小,并输出一种达到最优值的切法。

一份切法用 KK 个段的右端点 r1,…,rKr_1,\ldots,r_K 表示。它们满足

0=r0<r1<⋯<rK=n,0=r_0<r_1<\cdots<r_K=n,

第 ii 段包含 ari−1+1,…,aria_{r_{i-1}+1},\ldots,a_{r_i}。

输入格式

第一行两个整数 n,Kn,K。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出 KK 个整数,依次表示每段的右端点。

本题使用 Special Judge。若存在多种最优切法,输出任意一种即可。

数据范围

  • 1≤K≤n≤2000001\le K\le n\le 200000。
  • 0≤ai≤1090\le a_i\le10^9。

样例 1

5 3
2 4 7 3 5
2 3 5

三段为 [2,4][2,4]、[7][7]、[3,5][3,5],段和的最大值为 88,达到最优。

样例 2

4 3
0 0 0 0
1 2 4

1 3 4 也是一种正确输出。