====== Ocean View (Large) ======

===== 풀이 =====
  * [[ps:problems:boj:12354]]의 라지 버전. 풀이 및 코드는 동일하다. 
    * 라지버전임에도 불구, [[ps:tutorial:lis]]를 O(n^2)으로 구하더라도 충분히 통과한다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12355. Ocean View (Large)".

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

Tags: [lis]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.gcj_style
def main():
    N = int(sys.stdin.readline())
    h = [int(x) for x in sys.stdin.readline().split()]
    print(N - seqtask.longest_inc_subseq_length(h, strict=True))


if __name__ == '__main__':
    main()

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

{{tag>BOJ ps:problems:boj:실버_2}}