Problem Constraints and Intuition:

• Polycarp needs to solve n problems over k days.
• Each day, he must solve a contiguous sequence of problems from his list.
• The profit for each day is the maximum difficulty in the solved sequence.
• The goal is to maximize the sum of these daily profits.

Key Insight:

• To maximize the total profit, we should prioritize solving the most difficult problems on separate days. This is because the maximum in each day's subset contributes directly to the total profit.

Algorithm Selection:

• Sort the array of problem difficulties in descending order.
• Select the top k elements as the daily maxima.
• These top k values will be the maximums for each day, contributing the most to the total profit.

Daily Distribution Strategy:

• After sorting the array, the largest k elements will be the daily profit contributors.
• Distribute these elements such that each is the maximum of a contiguous segment, starting from the left of the array.

Implementation Steps:

• Read input values for n, k, and the array a.
• Sort a in descending order.
• Sum the top k elements to get the maximum total profit.
• Record the indices of these top k elements, ensuring they are distributed to form contiguous segments for each day.

Edge Cases:

• When k equals n, every day is a single problem, and the total profit is the sum of all elements.
• When all elements are the same, the profit is simply k times the value.
• When the largest elements are clustered, their positions must be carefully recorded to form valid contiguous segments.

Output:

• Print the total maximum profit.
• Print the distribution of problems into days, ensuring each day's segment is contiguous and correctly sequences the sorted top k elements.