탐욕적 증가 부분수열

면접 대비

시간 제한1초메모리 제한512 MB

요약

순열이 주어질 때 이전에 고른 값보다 큰 원소 중 가장 왼쪽에 있는 것을 반복해서 골라 만들어진 부분 수열을 출력한다.

난이도: 보통10점 중 4점
유형: 배열, 시뮬레이션, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

$1, 2, \dots, N$ 의 순열 $A = (a_1, a_2, \dots, a_N)$ 이 주어질 때, 탐욕적 증가 부분수열(GIS)을 다음과 같이 정의한다.

$g_1 = a_1$ 이라 하자. $i > 1$ 인 각 $i$ 에 대해, $g_i$ 는 $A$ 에서 $g_{i-1}$ 보다 큰 수 중 가장 왼쪽에 있는 수라 하자. 만약 주어진 $i$ 에 대해 그러한 수가 없다면, 수열의 GIS는 $(g_1, g_2, \dots, g_{i-1})$ 이라 한다.

순열 $A$ 가 주어질 때, $A$ 의 GIS를 구하시오.

입력

입력의 첫째 줄에는 순열 $A$ 의 원소 개수를 나타내는 정수 $1 \le N \le 10^6$ 이 주어진다. 다음 줄에는 $1$ 과 $N$ 사이의 서로 다른 정수 $N$ 개, 즉 순열 $A$ 의 원소 $a_1, \dots, a_N$ 이 주어진다.

출력

먼저 $A$ 의 GIS의 길이 $l$ 을 한 줄에 출력한다. 그다음 $l$ 개의 정수를 GIS의 원소 순서대로 출력한다.

예제3

예제 1
입력
```
7
2 3 1 5 4 7 6
```
예상 출력
```
4
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
```