## DMOPC '21 Contest 3 P4 - Sorting Subsequences

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

You are given a permutation of . In one operation, you may select any subsequence of consisting of no more than elements and sort the elements of that subsequence in increasing order. However, each element of may only be selected in at most one operation. Given these conditions, determine the lexicographically smallest permutation possible after performing some number of operations.

#### Constraints

is a permutation of .

#### Input Specification

The first line contains integers and .

The second line contains integers .

#### Output Specification

Output integers on a single line, representing the lexicographically smallest permutation possible after performing some number of operations.

#### Sample Input

8 3
4 7 6 2 8 3 1 5

#### Sample Output

1 2 3 5 4 6 8 7

#### Explanation

In the first operation, we may select the subsequence consisting of the elements at indices and . Sorting this subsequence yields .

Then, we may select the subsequence consisting of the elements at indices , , and . Sorting this subsequence yields .

Finally, we may select the subsequence consisting of the elements at indices , , and . Sorting this subsequence yields .