====== Ocean View (Small) ======

===== 풀이 =====
  * 남은 집들이 오름차순으로 정렬된 상태가 되면, 모든 집들이 오션뷰를 볼수 있다.
  * 오름차순으로 정렬된 가장 많은 집의 개수는, [[ps:tutorial:lis]]의 길이를 구하면 된다. 부숴야 하는 집의 개수는, 전체 개수에서 남길 집의 개수를 빼주면 된다.
  * LIS를 구하는 시간복잡도는 O(nlogn)

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

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

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:실버_5}}