FJ có \(N\) cô bò (\(1 \leq N \leq 10^5\)), được định danh riêng biệt từ \(1 \ldots N\) và xếp thành một hàng. FJ thích các cô bò được sắp xếp theo thứ tự tăng dần, nhưng đáng tiếc là hiện tại chúng đang lộn xộn. Trước đây FJ từng dùng những thuật toán đột phá như "bubble sort" để sắp xếp các cô bò, nhưng hôm nay ông cảm thấy khá lười. Thay vào đó, mỗi lần ông sẽ quát một cô bò cụ thể rằng hãy "tự sắp xếp đi". Khi bị quát, một cô bò sẽ đảm bảo rằng mình không đứng sai thứ tự (theo góc nhìn của cô). Chừng nào cô bò ngay bên phải có ID nhỏ hơn, hai cô sẽ đổi chỗ cho nhau. Sau đó, chừng nào cô bò ngay bên trái có ID lớn hơn, hai cô sẽ đổi chỗ cho nhau. Cuối cùng, cô bò hoàn tất việc "tự sắp xếp"; lúc này cô bò bên trái cô có ID nhỏ hơn và cô bò bên phải cô có ID lớn hơn.

FJ muốn chọn một tập con các cô bò, rồi duyệt qua tập con này và lần lượt quát từng cô (theo thứ tự ID tăng dần), lặp đi lặp lại cho đến khi tất cả \(N\) cô bò được sắp xếp. Chẳng hạn, nếu chọn tập con gồm các cô bò có ID \(\{2, 4, 5\}\), ông sẽ quát cô bò \(2\), rồi cô bò \(4\), rồi cô bò \(5\). Nếu \(N\) cô bò vẫn chưa được sắp xếp, ông sẽ tiếp tục quát lại chính những cô bò này nhiều lần nữa nếu cần.

Vì FJ không chắc những cô bò nào đang chú ý, ông muốn tối thiểu hóa kích thước của tập con này. Ngoài ra, FJ cho rằng số \(K\) rất may mắn. Hãy giúp ông tìm tập con có kích thước nhỏ nhất đứng thứ \(K\) theo thứ tự từ điển sao cho việc quát các cô bò trong đó nhiều lần cuối cùng sẽ khiến tất cả các cô bò được sắp xếp.

Một tập con \(S\) của \(\{1,\dots,N\}\) được gọi là nhỏ hơn tập con \(T\) theo thứ tự từ điển nếu danh sách các phần tử của \(S\) (theo thứ tự tăng dần) nhỏ hơn danh sách các phần tử của \(T\) (theo thứ tự tăng dần) theo thứ tự từ điển. Chẳng hạn, \(\{1, 3, 6\}\) nhỏ hơn \(\{1, 4, 5\}\) theo thứ tự từ điển.

Phân nhóm

• Các trường hợp chiếm \(3/16\) số điểm có \(N \leq 6\) và \(K = 1\).
• Các trường hợp bổ sung chiếm \(5/16\) số điểm có \(K = 1\).
• Các trường hợp bổ sung chiếm \(8/16\) số điểm không có thêm ràng buộc nào.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất \(N\). Dòng thứ hai chứa một số nguyên duy nhất \(K\) (\(1 \leq K \leq 10^{18}\)). Dòng thứ ba chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn số hiệu của các cô bò từ trái sang phải.

Đảm bảo rằng có ít nhất \(K\) tập con hợp lệ.

Dữ liệu ra

Dòng đầu tiên chứa kích thước của tập con nhỏ nhất. Các dòng còn lại chứa ID của các cô bò trong tập con có kích thước nhỏ nhất đứng thứ \(K\) theo thứ tự từ điển, mỗi dòng một ID và được liệt kê theo thứ tự tăng dần.

Ví dụ

4 1
4 2 1 3

2
1
4

Nguồn

Đề bài gốc: USACO 2018 December Contest, Platinum — Sort It Out

Tác giả: Spencer Compton