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를 계산하는 것이다.

#8714 upload 27 done 18 how_to_reg 17

Greedily Increasing Subsequence timer 1s memory 512MB

#8714

Greedily Increasing Subsequence 1s 512MB