====== 줄세우기 ======

===== 풀이 =====
  * [[ps:tutorial:lis]]의 크기를 구해서, N에서 빼주면 된다. ([[ps:tutorial:lis#정렬 문제]] 참고)
  * LIS만 구하면 되므로, 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2631. 줄세우기".

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

Tags: [LIS]
"""

from teflib import seqtask


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


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:seqtask#longest_inc_subseq|teflib.seqtask.longest_inc_subseq]]

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