Jealous Split

주어진 배열을 정확히 k개의 비어 있지 않은 연속 구간으로 나누되, 이웃한 두 구간의 합 차이가 두 구간 최댓값 중 큰 값 이하가 되도록 하는 분할 하나를 출력하거나 불가능하면 불가능함을 보고한다.

어려움8그리디누적 합이분 탐색구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

You have an array of non-negative integers a1, a2, . . . , an.

You need to split it into k non-empty subsegments: [1; b1], [b1 + 1; b2], . . . , [bk−1 + 1; n].

Let us denote the sum on i-th segment as si and the maximum on i-th segment as mi. Your goal is to make |si − si+1| ≤ max(mi, mi+1) for each 1 ≤ i ≤ k − 1.

입력

The first line of the input contains two integers n and k: the size of the array and the required number of segments (3 ≤ k ≤ n ≤ 100 000).

The next line contains n integers a1, a2, . . . , an: the given array (0 ≤ ai ≤ 50 000).

출력

If splitting is possible, print “Yes” on the first line, and then print k − 1 space-separated integers b1, b2, . . . , bk−1 on the second line. The integers must satisfy 1 ≤ b1 < b2 < . . . < bk−1 < n. Additionally, the inequalities |si − si+1| ≤ max(mi, mi+1) must hold for each 1 ≤ i ≤ k − 1. If there are several possible solutions, print any one of them.

If splitting is impossible, print “No” on a single line.