https://www.acmicpc.net/problem/1365
1365번: 꼬인 전깃줄
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가
www.acmicpc.net
from bisect import bisect_left
n = int(input())
arr = list(map(int, input().split(" ")))
dp = [arr[0]]
for i in range(1, len(arr)):
if dp[-1] < arr[i]:
dp.append(arr[i])
else:
idx = bisect_left(dp, arr[i])
dp[idx] = arr[i]
print(dp)
