====== 가장 긴 증가하는 부분 수열 5 ======

===== 풀이 =====
  * [[ps:가장 긴 증가하는 부분 수열]]문제에서 트래킹을 추가한 버전. [[ps:problems:boj:14002]]와 동일하지만, N의 범위가 커졌기 때문에 O(nlogn) 알고리즘이 강제된다.
  * 풀이 방법과 트래킹 방법은 [[ps:가장 긴 증가하는 부분 수열]] 을 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 14003. 가장 긴 증가하는 부분 수열 5".

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

Tags: [LIS]
"""

from teflib import misc


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    lis = misc.LongestMonotoneSubsequence(A)
    print(lis.length)
    print(*lis.subsequence)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}