Problem:
		
E: LISum

		
問題

		

		長さ $N$ の数列 $A$ が与えられる。
		数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を求めよ。
		

		

		数列 $A$ の最長増加部分列とは、すべての $i < j$ で $A_i < A_j$ を満たす部分列のうち、最長なものを示す。
		

		
制約

		

			
入力値は全て整数である。

			
$1 \leq N \leq 10^5$

			
$0 \leq A_i \leq 10^5$

		

		
入力形式

		
 入力は以下の形式で与えられる。 

		

		$N$

		$A_1 \dots A_N$

		

		
出力

		
数列 $A$ の最長増加部分列のひとつを $B$ とするとき、$\sum B_i$ の最大値を出力せよ。また、末尾に改行も出力せよ。 

		
サンプル

		
サンプル入力 1

		

4
6 4 7 8

		
サンプル出力 1

		

21

		
最長増加部分列は $ (6, 7, 8)$ と $(4, 7, 8)$ である。よって最大値は $21$ である。

		
サンプル入力 2

		

3
1000 2 3

		
サンプル出力 2

		

5

		
最長増加部分列は $(2,3)$ のみである。

		
サンプル入力 3

		

7
17 17 13 4 20 12 15

		
サンプル出力 3

		

31

		
サンプル入力 4

		

7
19 16 14 9 4 20 2

		
サンプル出力 4

		

39



Sample input:
4
6 4 7 8


Sample output:
21

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int,input().split()))

lis = []
hist = []

for a in A:
    i = bisect.bisect_left(lis,a)
    if i == len(lis):
        lis.append(a)
        hist.append([a])
    else:
        lis[i] = a
        hist[i].append(a)

ans = last = hist[-1][0]
for row in reversed(hist[:-1]):
    i = bisect.bisect_left(row[::-1], last)
    last = row[-i]
    ans += last
print(ans)