====== Railway Transportation ======

===== 풀이 =====
  * {{myicon>g3}} [[ps:problems:boj:16288]]과 동일한 [[ps:tutorial:lis#수열을 최소 개수의 증가 부분 수열로 나누기]] 문제인데, 역추적이 붙어있는 형태이다
  * 각 원소들이 어떤 큐에 들어가는지를 추적하는 것도, 위 링크에서 설명했듯이 이분탐색으로 LDS를 구하는 알고리즘을 활용해서 처리 가능하다. 이것을 구하고 나면, pop연산이 발생하는 큐들의 번호 순서를 출력하는 것은, 그냥 원소들을 정렬한 뒤에 각 원소가 들어가있는 큐의 번호를 순서대로 써주면 된다. 


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 6656. Railway Transportation".

- Problem link: https://www.acmicpc.net/problem/6656
- Solution link: http://www.teferi.net/ps/problems/boj/6656

Tags: [LIS]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.run_until_all_zero
def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(x) for x in sys.stdin.readline().split()]

    lengths = seqtask.longest_dec_subseq_length_by_last_elem(nums, strict=True)
    if max(lengths) > M:
        print('Transportation failed')
    else:
        print(*lengths)
        print(*(lengths[i] for i in sorted(range(N), key=nums.__getitem__)))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_dec_subseq_length_by_last_elem|teflib.seqtask.longest_dec_subseq_length_by_last_elem]]

{{tag>BOJ ps:problems:boj:골드_2}}