잘못된 LIS 알고리즘

정현이와 서준이는 정보과학 시간에 수열의 LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)의 길이를 구하는 알고리즘을 배웠다. 그런데 정현이는 이 알고리즘을 구현하는 것이 너무 귀찮았던 나머지, 자신만의 (틀린) 알고리즘을 만들어 문제를 풀기 시작했다. 하지만 당연히 이 알고리즘으로는 문제를 풀 수 없었고, 숙제로 나온 온라인 저지 문제들에서 번번이 "틀렸습니다"를 받았다.

길이가 $N$이고 $i$번째 원소의 값이 $A_i$인 수열 $A$가 주어졌을 때, 정현이의 알고리즘은 다음 과정으로 수열 $B$를 만들어 반환한다.

B = 빈 수열
for i = 1부터 n까지:
    B가 비어 있거나, B의 마지막 원소가 A_i보다 작은 경우:
        B의 맨 뒤에 A_i를 추가

이 알고리즘이 반환하는 수열 $B$는 $A$의 증가하는 부분 수열이지만, 가장 긴 증가하는 부분 수열이라는 보장이 없으므로 잘못된 알고리즘이다. 서준이는 이 잘못을 알아채고 정현이에게 알려 주려 했지만, 정현이는 반례를 내놓으라며 납득하지 않는다.

서준이는 1부터 $N$까지의 양의 정수가 정확히 한 번씩 포함된 길이 $N$의 수열 중에서, 가장 긴 증가하는 부분 수열의 길이가 $M$이고 정현이의 알고리즘이 반환하는 증가하는 부분 수열의 길이가 $K$인 수열을 찾으려 한다. 서준이를 도와 이런 수열을 하나 찾아보자.

정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(2 \leq N \leq 300 000$; $1 \leq K < M \leq N)$

조건을 만족하는 수열이 존재하면, 그러한 수열 중 하나를 골라 $N$개의 원소를 순서대로 공백으로 구분하여 출력한다. 존재하지 않으면 -1을 출력한다.

수열 $A_i$의 가장 긴 증가하는 부분 수열은 $A_i$의 모든 부분 수열 중에서 가장 긴 증가하는 수열을 의미한다.

부분 수열은 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열이다.

증가하는 수열은 맨 처음 원소를 제외한 모든 원소가 바로 전 원소보다 큰 수열이다. 즉, 길이가 $N$인 수열 $C$에 대해 $C_{i-1} < C_i (2 \le i \le N)$를 만족하면 $C$는 증가하는 수열이다. 정의에 따라 길이가 1인 수열은 모두 증가하는 수열이다.

다음은 정현이의 알고리즘을 C++, Python 3, Java로 구현한 예시 코드이다.

C++

vector<int> b;
for(int x : a){
    if(b.empty() || b.back() < x){
        b.push_back(x);
    }
}

Python 3

b = []
for x in a:
    if not b or b[-1] < x:
        b.append(x)

Java

ArrayList<Integer> b = new ArrayList<Integer>();
for(int x : a){
    if(b.isEmpty() || b.get(b.size() - 1) < x){
        b.add(x);
    }
}