1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| from bisect import bisect_left
n = int(input())
arr = list(map(int, input().split()))
idx_list = [0] * (n + 1)
longest_array = [arr[0]]
for i, val in enumerate(arr):
if longest_array[-1] < val:
longest_array.append(val)
idx_list[i] = len(longest_array) - 1
else:
idx = bisect_left(longest_array, val)
longest_array[idx] = val
idx_list[i] = idx
print(len(longest_array))
ans = []
index = len(longest_array) - 1
for i in range(len(arr) - 1,-1,-1):
if idx_list[i] == index:
ans.append(arr[i])
index -= 1
print(*ans[::-1])
|