Bessie's Interview

Bessie is looking for a new job! Fortunately, there are currently \(K\) farmers recruiting and holding interviews. Since the application process is highly competitive, the cows are numbered in the order in which they applied. There are \(N\) cows who applied before Bessie, so her number is \(N+1\) (with \(1 \le K \le N \le 3\cdot10^5\)).

The interview process is as follows. At time \(0\), for every \(1 \le i \le K\), farmer \(i\) starts interviewing cow \(i\). Once a farmer finishes an interview, he immediately begins interviewing the next cow in line. If multiple farmers finish at the same time, the next cow waiting may choose any one of the available farmers based on her preference.

For each cow \(1 \le i \le N\), Bessie knows that the interview will take exactly \(t_i\) minutes (\(1\le t_i\le 10^9\)). However, she does not know the preferences of the cows when choosing among available farmers.

Because this job is very important to her, Bessie wants to prepare well. She needs to know when she will get interviewed and which farmers could possibly interview her. Help her determine these!

Note: The interview assignment works as a multi‐server queue. Initially, each farmer \(i\) (for \(1\le i\le K\)) is busy interviewing cow \(i\) until time \(t_i\). Then for each subsequent cow (from cow \(K+1\) to cow \(N\)), the cow is assigned to the farmer who becomes available the earliest (if there is a tie, the cow may choose any farmer among those finishing at the same time). Bessie is cow number \(N+1\). The interview start time for Bessie will be the minimum finishing time among all farmers after processing the first \(N\) cows, and if multiple farmers share that finishing time, then any one of them might interview her.

inputFormat

The first line contains two integers \(N\) and \(K\) representing the number of cows ahead of Bessie and the number of farmers, respectively.

The second line contains \(N\) integers, where the \(i\)-th integer \(t_i\) indicates the interview time (in minutes) for cow \(i\). It is guaranteed that \(1 \le t_i \le 10^9\) and \(1 \le K \le N \le 3\cdot10^5\).

outputFormat

Output a single line. First, print a single integer representing the time (in minutes) when Bessie will begin her interview. Then print the list of all possible farmer indices (in increasing order) who could interview her, separated by spaces.

For example, if the output is 4 1, it means Bessie starts her interview at time 4 and only farmer 1 can interview her. If the output is 5 1 3, it means Bessie starts at time 5, and either farmer 1 or farmer 3 may interview her depending on the choice.

sample

3 2
4 3 2

4 1