27989번 - 가장 큰 증가하는 부분 수열 2

길이가 N인 수열에서 0개 이상 N-1개 이하의 원소를 지워서 만든 수열 중, 길이가 1이거나 임의의 인접한 두 항 중 뒤의 항이 앞의 항보다 큰 수열을 증가 부분 수열이라고 한다.

양의 정수 N개로 이루어진 수열 A = {A₁, A₂, ⋯, A_N}이 주어졌을 때, 그 수열의 증가 부분 수열 중 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 {1, 9, 3, 6, 6, 7, 2, 4}의 증가 부분 수열 중 합이 가장 큰 것은 {1, 3, 6, 7}이고, 그 합은 17이다.

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 300,000)

둘째 줄에는 수열 A를 이루고 있는 양의 정수 A₁, A₂, ⋯, A_N이 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ A_i ≤ 10¹²)

수열 A의 증가 부분 수열 중 합이 가장 큰 것의 합을 출력한다.