• 남은 집들이 오름차순으로 정렬된 상태가 되면, 모든 집들이 오션뷰를 볼수 있다.
• 오름차순으로 정렬된 가장 많은 집의 개수는, 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)의 길이를 구하면 된다. 부숴야 하는 집의 개수는, 전체 개수에서 남길 집의 개수를 빼주면 된다.
• LIS를 구하는 시간복잡도는 O(nlogn)

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

• Dependency: teflib.seqtask.longest_inc_subseq_length