책정리

• 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)의 크기를 구해서, N에서 빼주면 된다. (정렬 문제 참고)
• LIS만 구하면 되므로, 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 1818. 책정리".

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

Tags: [LIS]
"""

from teflib import seqtask


def main():
    N = int(input())
    nums = [int(x) for x in input().split()]
    print(N - seqtask.longest_inc_subseq(nums))


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq