from bisect import *
N = int(input())
seq = [*map(int,input().split())]
DP = [0]
for n in seq:
if n>DP[-1]:
DP.append(n)
else:
DP[bisect_left(DP,n)] = n
print(N+1-len(DP))
전깃줄 - 2 [백준 2568번] 전깃줄 -2 (Python3) (tistory.com) 문제의 하위호환 문제
N과 LIS 길이의 차를 출력해주면 된다.
여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.