Let's think about what happens to our list of cows as FJ continues to yell our chosen subset. Every time a cow chooses to swap position with an adjacent cow, the number of inversions in our list decreases by exactly one. This shows us that eventually the process must stop.

What can we say about our list of cows when the process finishes? We can be certain that no two adjacent cows are both in our subset and in the wrong order. Otherwise, we would simply swap their positions with another iteration of the process. Another thing we know is that all cows not in our set have the same relative order as they originally did. This is because no two such cows will ever swap positions. It's then clear that it is necessary for all cows not in our set to make an increasing subsequence in our original list.

Now we think about what we can say about the final state of our list when the complement of our set forms an increasing subsequence. We already know any two adjacent cows in our set will be in the correct order. From this, we can conclude that any contiguous segment of cows that are all in our set must be in the correct order. We can visualize the structure of our final array as sorted segments of cows in our set with cows not in our set sandwiched between these segments. With this visualization, it is easy to see that any of these segments will have cows with IDs strictly in the range of the two cows not in our set that sandwich the segment. We now see that any segment to the left of another segment must have IDs that are all strictly smaller than the segment to the right. It is now clear that all pairs of "types" of cows must be in order. Meaning, any two cows that are in our set must be in the correct order, any two cows not in our set must be in the correct order (by definition), and we can also see that there won't be pair of a cow in our set and a cow not in our set that are out of order. Thus, if the cows not in our set are an increasing subsequence then eventually our list will be sorted.

How do we choose the smallest set where its complement is an increasing sequence? We choose a set where its complement is a Longest Increasing Subsequence (LIS). Finding the length of the LIS is a classic problem and can be done in $O(N\log{N})$ time. What about finding the $K$-th lexicographically smallest set? We use the complement of the $K$-th lexicographically largest LIS.

How do we find the $K$-th lexicographically largest LIS? Let $lis[i]$ denote the largest increasing subsequence starting with the cow who is at position $i$. Let $a[i]$ denote the ID of the cow at position $i$. To calculate $lis[i]$ it is $1 + lis[j]$ where $j$ is the maximal $lis[j]$ given $i<j$ and $a[i] < a[j]$. This can be calculated in a manner similar to computing LIS with a segment tree. From this formulation, consider two cows at position $i$ and $j$ where $i<j$ and $lis[i]=lis[j]$.

Now we will compute $dp[i]$ which is the number of LIS that are of length $lis[i]$ and start at position $i$. We can see that $dp[i]$ is equal to the sum of all $dp[j]$ where $i<j$, $a[i] < a[j]$, and $lis[j] = lis[i]-1$. To calculate $dp[i]$ we can make a separate segment tree for each group of elements that have the same value of $lis[i]$ and then calculate the answer using a sweep similar to that of calculating the LIS. Note that $dp[i]$ can be very large, so we will just store the minimum of $dp[i]$ and $K+1$ for the value held in each $dp[i]$ and in our segment tree's nodes.

Once we have all $dp[i]$, we just need to reconstruct the $K$-th largest LIS. To determine the $x$-th element (0-indexed) of the LIS, we process nodes where $lis[i] = $ (length of the LIS) $- x$ in decreasing order of ID. Let $i$ be the position of the $x-1$-th element in the LIS we're building and let $j$ be the position of the element we are considering. We will ignore the element if $j<i$ or $a[j] < a[i]$. Otherwise, if $dp[j]<K$, then the $K$-th LIS does not use this element. We will subtract $dp[j]$ from $K$ and continue. If $dp[j] \geq K$ then we will use that element and continue onto considering the $X+1$-th element of our LIS.

Once we have computed the $K$-th lexicographically largest LIS we will simply take its complement.

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll inf = 1000000000000000000LL; class Node{ public: Node *l, *r; int s, e; ll sum, maxi; Node(int a, int b){ s = a; e = b; maxi = 0LL; sum = 0LL; if(s!=e){ l = new Node(s,(s+e)/2); r = new Node((s+e)/2+1,e); } } void pull(){ if(s==e){ return; } sum = l->sum + r->sum; sum = min(sum,inf); maxi = max(l->maxi,r->maxi); } void add(int ind, ll val){ if(s==ind && e==ind){ sum += val; sum = min(sum,inf); maxi = sum; return; } if(ind<=(s+e)/2){ l->add(ind,val); } else{ r->add(ind,val); } pull(); } ll gsum(int st, int en){ if(st<=s && e<=en){ return sum; } ll ret = 0LL; if(st<=(s+e)/2){ ret += l->gsum(st,en); } if(en>(s+e)/2){ ret += r->gsum(st,en); } ret = min(ret,inf); return ret; } ll getmax(int st, int en){ if(st<=s && e<=en){ return maxi; } ll ret = 0; if(st<=(s+e)/2){ ret = max(ret,l->getmax(st,en)); } if(en>(s+e)/2){ ret = max(ret,r->getmax(st,en)); } return ret; } }; int main(){ ifstream in("itout.in"); ofstream out("itout.out"); int n; ll k; in >> n >> k; int a[n]; for(int i = 0; i<n; i++){ in >> a[i]; } Node *t = new Node(1,n); int lis[n]; int best = 0; //lis starting with this node for(int i = n-1; i>=0; i--){ lis[i] = 1 + t->getmax(a[i],n); t->add(a[i],lis[i]); best = max(best,lis[i]); } vector<ll> dp[best]; vector<Node*> seg; vector<int> nums[best]; vector<int> loc[best]; vector<int> point; int id[n]; for(int i = n-1; i>=0; i--){ lis[i]--; id[i] = nums[lis[i]].size(); nums[lis[i]].push_back(a[i]); loc[lis[i]].push_back(i); dp[lis[i]].push_back(0LL); } for(int i = 0; i<best; i++){ point.push_back(0); seg.push_back(new Node(0,(int)nums[i].size())); } for(int i = n-1; i>=0; i--){ if(lis[i]==0){ dp[lis[i]][id[i]] = 1LL; seg[lis[i]]->add(id[i],1LL); continue; } ll cur = 0LL; while(point[lis[i]]<nums[lis[i]-1].size() && a[i] > nums[lis[i]-1][point[lis[i]]]){ point[lis[i]]++; } cur = seg[lis[i]-1]->gsum(point[lis[i]],nums[lis[i]-1].size()); dp[lis[i]][id[i]] = cur; seg[lis[i]]->add(id[i],cur); } ll rem = k; bool inAns[n+1]; for(int i = 1; i<=n; i++){ inAns[i] = true; } int prev = -1; for(int i = best-1; i>=0; i--){ int use = nums[i].size()-1; while(loc[i][use]<prev){ use--; } while(dp[i][use]<rem){ rem -= dp[i][use--]; } prev = loc[i][use]; inAns[nums[i][use]] = false; } int sz = 0; for(int i = 1; i<=n; i++){ if(inAns[i]){ sz++; } } out << sz << endl; for(int i = 1; i<=n; i++){ if(inAns[i]){ out << i << endl; } } return 0; }