K-th Minimal Shouting Subset

Farmer John has N cows labeled 1,…,N standing in a line in an arbitrary order. He prefers the cows to be in increasing order by label, but today the order is scrambled. In the past he might have used algorithms like bubble sort to fix the order, but today he is lazy. Instead, he selects a subset S of cows and repeatedly shouts to them in the order of increasing cow labels (that is, in increasing order of their IDs). When a cow is shouted at, she performs the following procedure:

1. While the cow immediately to her right has a smaller label than hers, they swap places.
2. Then, while the cow immediately to her left has a larger label than hers, they swap places.

After these swaps the cow has ensured that, from her own perspective, all cows to her left have smaller labels and all cows to her right have larger labels.

Farmer John will cycle through the cows in S (in increasing order of their labels), shout at each one, and if necessary repeat this process, until the entire lineup is in sorted order. However, since some cows may not pay attention, FJ wishes to keep S as small as possible while still guaranteeing that repeated shouts will eventually sort all the cows.

Moreover, FJ considers the number K to be lucky. Among all subsets S of minimum possible size (so that shouting repeatedly at those cows eventually sorts the cows), the lexicographically K-th smallest (when S is written in increasing order) is the one he chooses. Here, for two subsets S and T of {1,…,N}, we say S is lexicographically smaller than T if the sorted sequence of elements in S is lexicographically smaller than that for T. For example, {1,3,6} is lexicographically smaller than {1,4,5} because the sequence (1,3,6) is lexicographically smaller than (1,4,5).

Your task is to help FJ. Given the number N, the lucky number K, and the current ordering of the cows (by their labels), find and output the lexicographically K-th smallest subset S (with minimum possible size) with the property that if FJ repeatedly shouts at the cows in S (in increasing order of their labels) the cows will eventually be sorted.

---

Problem Modeling

A key observation is that any cow that never needs to be shouted at will eventually appear in an increasing sequence when reading the current lineup. In fact, if you remove from the lineup the cows that are shouted at, the remaining cows must form a strictly increasing sequence. Furthermore, to minimize |S| the remaining subsequence must be as long as possible – in other words, it must be a longest increasing subsequence (LIS) of the input permutation. Thus the minimal shouting subset S is exactly the complement (w.r.t. {1,…,N}) of some longest increasing subsequence T. Since many different longest increasing subsequences may exist, many valid minimal subsets S exist. You are to output the lexicographically K-th smallest S (when its elements are listed in increasing order).

Input and Output

The input starts with two integers: N and K. The next line contains N distinct integers which represent the labels of the cows in their current order (from left to right).

The output should first print the size of the subset S and then the cow labels in S in increasing order, each separated by whitespace (or on separate lines).

inputFormat

The first line contains two integers N (1 ≤ N ≤ 10⁵) and K (1 ≤ K ≤ number of minimal subsets). The second line contains N distinct integers, a permutation of {1,…,N}, representing the order of cows from left to right.

Example 1:

3 1
3 1 2

Example 2:

5 1
2 3 1 5 4

Example 3:

5 2
2 3 1 5 4

outputFormat

On the first line output the size of the minimal subset S (which is N minus the length of a longest increasing subsequence). Then output the elements of S in increasing order (by cow label). For instance, for Example 1 the output is:

1
3

sample

3 1
3 1 2

1
3

</p>