페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8714

탐욕적으로 증가하는 부분수열 1s 512MB

문제

1,2,…,N 의 순열 A = (a_1, a_2, \dots, a_N) 가 주어졌을 때, 우리는 다음과 같은 방식으로 “탐욕적으로 증가하는 부분수열(GIS, greedily increasing subsequence)”을 정의한다.

먼저 g_1 = a_1 이다. 모든 i > 1 에 대해, g_i​ 는 g_{i-1}​ 보다 엄격히 큰(g_{i-1} < g_i) 정수 중에서 A 안에서 가장 왼쪽에 있는 정수이다. 만약 어떤 i 에 대해 그런 정수가 존재하지 않는다면, 그때의 GIS는 수열 (g_1, g_2, ..., g_{i-1})이라고 한다.

당신의 작업은, 주어진 순열 A 에 대해 GIS를 계산하는 것이다.


입력

입력의 첫 줄에는 정수 N (1 \le N \le 10^6) 이 주어지며, 이는 순열 A 의 원소 수이다.
다음 줄에는 1 이상 N 이하의 서로 다른 정수 N개, 즉 순열 A 의 원소 a_1, \dots, a_N 이 주어진다.


출력

먼저 GIS의 길이 L을 한 줄에 출력한다.

그 다음 줄에는 GIS의 원소 L개를 순서대로 출력한다.


예제 #1

7
2 3 1 5 4 7 6
4
2 3 5 7

\{2,3,1,5,4,7,6\} 에서 먼저 g_1 = 2 이다.
2보다 큰 값 중 가장 왼쪽에 있는 정수는 3이므로 g_2 = 3
3보다 큰 값 중 가장 왼쪽에 있는 정수는 5이므로 g_3 = 5.
5보다 큰 값 중 가장 왼쪽에 있는 정수는 7이므로 g_4 = 7.
마지막으로 7보다 큰 정수는 없다.
따라서 순열 \{2,3,1,5,4,7,6\} 의 GIS는 \{2,3,5,7\} 이다.


예제 #2

5
1 2 3 4 5
5
1 2 3 4 5

예제 #3

5
5 4 3 2 1
1
5


출처

HiQ Challenge 2017 B번
로그인해야 코드를 작성할 수 있어요.