+ محدودیت زمان: ۱/۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + روز ۳ دوره ۳۰ ---------- ابوالفضل $n$ هندوانه را در یک ردیف چیده‌است. او می‌خواهد به هر هندوانه یک عدد طبیعی متمایز بین $1$ تا $n$ اختصاص بدهد. سپس در ابتدای هر روز، هر هندوانه‌ای که عددی کوچک‌تر از هندوانه‌ی سمت راست خود (در صورت وجود) دارد را انتخاب کند و همه‌ی آن‌ها را در همان روز بخورد. برای مثال اگر اعداد روی هندوانه‌ها $\langle 1, 5, 2, 4, 6,3\rangle $ باشد، بعد از یک روز تبدیل به $\langle 5, 6 ,3\rangle $ و بعد از یک روز دیگر تبدیل به $\langle 6 , 3\rangle $ می‌شود و در روزهای بعدی تغییری نمی‌کند. در این مثال، ابوالفضل هندوانه‌های اول (با شماره‌ی $1$)، سوم (با شماره‌ی $2$) و چهارم (با شماره‌ی $4$) را در روز اول، و هندوانه‌ی دوم (با شماره‌ی $5$) را در روز دوم می‌خورد و هندوانه‌های پنجم (با شماره‌ی $6$) و ششم (با شماره‌ی $3$) را هرگز نمی‌خورد. یک عدددهی به هندوانه‌ها «ابوالفضل‌پسند» است اگر به ازای هر $i$ در صورتی که $b_i = -1$ باشد هندوانه‌ی $i$ام هیچ‌وقت خورده نشود و در غیر این صورت در روز $b_i$ خورده شود. به ابوالفضل $k$امین زیباترین عدددهی ابوالفضل‌پسند را بگویید. یک جایگشت $p_1, p_2, ..., p_n$ از جایگشت $q_1,q_2,...,q_n$ زیبا‌تر است اگر مقدار $i$ وجود داشته باشد که به ازای هر $j < i$ جایگاه $k$ وجود داشته باشد که $p_k = j$ و $q_k = j$ و اگر $p_x = i$ و $q_y = i$ باشد، $x < y$ نیز برقرار باشد.توجه کنید که زیباتر بودن با کوچک‌تر بودن از نظر کتاب‌خانه‌ای تفاوت دارد. می‌توان اثبات نمود که اگر جایگشت $p$ از جایگشت $q$ و جایگشت $q$ از جایگشت $r$ زیباتر باشد، آن‌گاه جایگشت $p$ از جایگشت $r$ نیز زیباتر است. # ورودی در خط اول ورودی $n$، تعداد هندوانه‌ها و سپس $k$ به ترتیب می‌آیند. در خط بعدی $n$ عدد $b_1, b_2, ..., b_n$ به‌ترتیب می‌آیند. $$1 \le n \le 10^{5}$$ $$1 \le k \le 10$$ $$-1 \leq b_i \leq n$$ $$b_i \neq 0$$ # خروجی اگر کمتر از $k$ عددگذاری ابوالفضل‌پسند وجود داشت $-1$ و در غیر این صورت $k$امین زیبا‌ترین عددگذاری ابوالفضل‌پسند را خروجی دهید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۷ | $n \le 10$ | | ۲ | ۲۵ | $n \le 2000$ | | ۳ | ۳۱ | $k \le 1$ | | ۴ | ۱۸ | $k \le 2$ | | ۵ | ۱۹ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 1 1 2 1 -1 -1 ``` ## خروجی نمونه ۱ ``` 1 3 2 5 4 ``` ## ورودی نمونه ۲ ``` 5 2 1 2 1 -1 -1 ``` ## خروجی نمونه ۲ ``` 1 4 2 5 3 ``` ## ورودی نمونه ۳ ``` 5 10 1 2 1 -1 -1 ``` ## خروجی نمونه ۳ ``` -1 ```

حل سؤال در بانک سؤالات