26717번 - Podwyżki 스페셜 저지다국어

2022 był dla firmy Bajtcorp ciężkim rokiem. Złe decyzje biznesowe w połączeniu z nieciekawą sytuacją na rynku sprawiły, że firmy nie stać na podwyżki dla swoich pracowników. W ramach przygotowania się na niekomfortowe pytania ze strony zatrudnionych, dział HR wynalazł sposób udowodnienia, że pracownik nie zasługuje na podwyżkę.

Na podstawie danych o sumarycznych przychodach generowanych przez pracownika w kolejnych dniach można podzielić rok (który w Bajtocji wcale nie musi mieć 365 dni) na przedziały czasu, które będą wskazywały na to, że ten nie rozwija się w pracy. Dokładniej, dział HR chciałby podzielić ciąg przychodów na k spójnych przedziałów tak, aby każdy element ciągu należał do dokładnie jednego przedziału. Podział jest poprawny, jeżeli nie jest możliwe wybranie po jednym elemencie z każdego przedziału w taki sposób, żeby wybrane elementy tworzyły ciąg ściśle rosnący.

Przyszłość Bajtcorpu jest w Twoich rękach. Napisz program, który wczyta ciąg przychodów generowanych przez pewnego pracownika oraz liczbę k, a następnie podzieli go na k przedziałów zgodnych z wytycznymi działu HR lub stwierdzi, że jest to niemożliwe.

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n i k (2 ≤ k ≤ n ≤ 500 000), oznaczające odpowiednio długość ciągu przychodów generowanych przez pracownika oraz wymaganą liczbę przedziałów.

Kolejny wiersz składa się z n liczb całkowitych a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹), które tworzą ciąg przychodów.

Jeżeli nie da się podzielić ciągu zgodnie z wytycznymi, to w jedynym wierszu wyjścia powinien znaleźć się napis ‘NIE’.

W przeciwnym wypadku w pierwszym wierszu należy wypisać napis ‘TAK’, a w drugim wierszu ciąg k − 1 liczb v₁, . . . , v_k−1 (1 ≤ v_i < n; v_i < v_i+1), będących indeksami końców kolejnych przedziałów w poprawnym podziale, poza końcem ostatniego przedziału, który zawsze kończy się w indeksie n.

Jeżeli istnieje wiele poprawnych odpowiedzi, to wypisz dowolną z nich.

Wyjaśnienie przykładów: W pierwszym teście przykładowym po podzieleniu ciągu na przedziały [3, 5, 4], [8, 3] i [7] niezależnie od tego który element wybierzemy w pierwszym podciągu, w drugim będziemy musieli wybrać 8, żeby tworzyły ciąg rosnący. W ostatnim podciągu mamy tylko jeden wybór, który nie jest większy od 8, zatem nie jesteśmy w stanie stworzyć rosnącego ciągu i podział jest zgodny z wytycznymi.