Minimizing Cable Car Support Posts

The mountains of Colorado are represented by a broken line in the 2D plane. This polyline consists of N endpoints and N-1 segments. The i-th endpoint has an x-coordinate of i and a y-coordinate of \(H_i\), where \(H_i\) represents the height (or altitude).

Ron plans to build a ski resort for his cows by installing a cable car system. The cable car line is also a polyline composed of several segments. The cable starts at the first endpoint of the mountain and ends at the last endpoint. Each cable segment can either follow the mountain contour or be suspended in the air, effectively skipping several low-altitude endpoints. However, each cable segment has a constraint on its horizontal span: it cannot exceed the given integer \(K\). At the endpoints of each cable segment, a support post must be built to secure the cable. Note that posts must be built at the starting and ending points of the mountain.

Your task is to help Ron decide which mountain endpoints should have support posts so that the total number of posts is minimized.

Hint: You are given \(N\) (the number of endpoints), \(K\) (the maximum horizontal span each cable segment can cover), and the heights \(H_1, H_2, \dots, H_N\) of the mountain endpoints. The cable segments can jump over some endpoints as long as the horizontal distance between consecutive chosen endpoints does not exceed \(K\). The optimal strategy is to cover the maximum possible horizontal distance with each cable segment.

Note: Even though the mountain heights are provided, they do not affect the planning because the cable can be suspended in the air.

inputFormat

The first line of input contains two integers: \(N\) and \(K\), where \(N\) (\(2 \leq N \leq 10^5\)) is the number of mountain endpoints and \(K\) (\(1 \leq K \leq N-1\)) is the maximum horizontal span allowed for each cable segment.

The second line contains \(N\) integers: \(H_1, H_2, \ldots, H_N\), where \(H_i\) represents the height (or altitude) of the \(i\)-th endpoint.

Endpoints are numbered from 1 to \(N\) according to their x-coordinates.

outputFormat

Output two lines. The first line should contain a single integer representing the minimum number of support posts required. The second line should list the indices of the selected endpoints (in increasing order) where the posts should be built.

It is guaranteed that a solution exists where the first and last endpoints are always selected.

sample

5 2
100 200 150 180 120

3
1 3 5