Sırala

FJ-nin $n$ inəyi (fərqli 1, \ldots, n ID-ləri ilə) bir sırada düzülüb. FJ öz inəklərinin ID-lərinin artan qaydada sıralanmasını sevir, ancaq təəssüf ki, onlar hazırda düzgün sırada deyillər. Baxmayaraq ki, keçmişdə FJ inəklərini sıralamaq üçün "bubble sort" kimi inqilabi alqoritmlərdən istifadə edib, bu gün o özünü olduqca tənbəl hiss edir. Bunun əvəzinə, o, bir-bir, müəyyən inəklərə "sırana düş" deyə qışqıracaq. Qışqırılan zaman, inək özünün (öz nöqteyi-nəzərindən) sırada olub-olmadığını yoxlayır. Onun sağındakı inəyin ID-si daha kiçik olduğu müddətcə, onlar yerlərini dəyişirlər. Sonra, onun solundakı inəyin ID-si daha böyük olduğu müddətcə, onlar yerlərini dəyişirlər. Bundan sonra, inək "sıraya düşmə" prosesini bitirmiş olur: onun solundakı inəyin ID-si daha kiçikdir, sağındakı inəyin ID-si isə daha böyükdür.

FJ inəklərdən bir alt çoxluq seçmək və sonra bütün $n$ inək sıralanana qədər, bu alt çoxluqdakı hər bir inəyə növbə ilə (ID-lərin artan sırası ilə) dəfələrlə qışqırmaq istəyir. Məsələn, əgər o, ID-ləri \{2, 4, 5\} olan inəklərin alt çoxluğunu seçərsə, o, əvvəlcə $2$ nömrəli inəyə, sonra $4$ nömrəli inəyə, sonra isə $5$ nömrəli inəyə qışqıracaq. Əgər $n$ inək hələ də sıralanmayıbsa, o, eyni inəklərə lazım olduğu qədər dəfələrlə təkrar-təkrar qışqıracaq.

FJ hansı inəklərin diqqət etdiyinə əmin olmadığı üçün, bu alt çoxluğun ölçüsünü minimuma endirmək istəyir. Bundan əlavə, FJ $k$ ədədini çox uğurlu hesab edir. Ona kömək edin ki, bu alt çoxluqdakı inəklərə təkrar-təkrar qışqırmaq nəticəsində bütün inəklərin sıralanmasına nail olacaq minimum ölçülü alt çoxluqlar arasından $k$-ıncı leksikoqrafik olaraq ən kiçik olanı tapsın.

\{1, \ldots, n\} çoxluğunun $S$ alt çoxluğu, $T$ alt çoxluğundan leksikoqrafik olaraq kiçikdir, əgər $S$-in elementlərinin siyahısı (artan sırada) $T$-nin elementlərinin siyahısından (artan sırada) leksikoqrafik olaraq kiçikdirsə. Məsələn, \{1, 3, 6\} çoxluğu \{1, 4, 5\} çoxluğundan leksikoqrafik olaraq kiçikdir.