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

• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)문제에서 트래킹을 추가한 버전. 가장 긴 증가하는 부분 수열 4와 동일하지만, N의 범위가 커졌기 때문에 O(nlogn) 알고리즘이 강제된다.
• 풀이 방법과 트래킹 방법은 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS) 을 참고.

"""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()