Not the Longest Increasing Subsequence

Time limit2sMemory limit512 MB

Summary

Given an array of n integers from 1 to k, find the fewest elements to delete so that its longest increasing subsequence has length less than k, and list their indices.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Array
Solved: No attempts yet

Problem

You have an array of $n$ integers. Each element $a_i$ is between $1$ and $k$ . What is the smallest number of elements that must be removed from the array so that its longest increasing subsequence has length less than $k$ ?

Input

The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^6$ , $1 \le k \le n$ ), the length of the array and the upper bound for its elements. The second line contains $n$ integers $a_i$ ( $1 \le a_i \le k$ ), the elements of the array.

Output

In the first line, output an integer $m$ , the number of elements to remove. In the second line, output $m$ integers, the indices of the removed elements. The indices are numbered from $1$ to $n$ .

Examples3

Example 1
Input
```
3 2
1 2 2
```
Expected output
```
1
1
```
Example 2
Input
```
2 2
2 1
```
Expected output
```
0
```
Example 3
Input
```
8 3
1 2 2 1 1 3 2 3
```
Expected output
```
2
1 7
```