[KOITP] 증가 부분수열 나누기(Not Solved)

출    처 : http://koitp.org/problem/IS_GROUP/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
2.0 초	512 MB	12	2 (17%)	1

문제

크기가 $N$인 정수로 이루어진 수열이 있다. 이 수열을 여러 개의 증가 부분수열로 나누는데, 수열의 한 원소는 반드시 한 개의 부분 수열에 속해야한다. 이 때, 필요한 증가 부분수열의 최소 개수를 구하는 프로그램을 작성하시오.

부분 수열(Subsequence)은 어떤 수열에서 순서를 유지하되, 그 중 일부 항만을 선택하여 만들 수 있는 수열이다. 예를 들어, $[1,3,2,4]$로 이루어진 수열이 있다면, $[1,3,4]$, $[1,2,4]$등은 부분 수열이 될 수 있지만, $[1,2,3]$은 부분수열이 될 수 없다.

증가 부분수열(Increasing subsequence)이란, 부분수열 중에 수열의 원소가 오른쪽으로 갈 수록 증가하는 부분수열을 의미한다. 이 문제에서 수가 같은 경우 증가하지 않는 것으로 간주한다.

예를 들어, $[3,1,2,5,3]$은 $[3,5]$, $[1,2,3]$ 두 개의 증가 부분수열로 나눌 수 있고, 한 개의 증가 부분수열로 나눌 수 없으므로, 필요한 증가 부분수열의 최소 개수는 $2$개가 된다.

입력

첫 줄에 수열의 크기를 나타내는 자연수 $N$이 주어진다. ($1\le N\le 300,000$)

둘째 줄에 수열의 원소를 나타내는 자연수 $N$개가 공백으로 구분되어 순서대로 주어진다. 주어지는 수는 ${10}^9$을 넘지 않는다.

출력

첫 줄에 필요한 증가 부분수열의 최소 개수 $k$를 출력한다.

그 다음 $k$개의 줄에 증가 부분수열에 대한 정보를 출력한다. $i+1$번째 줄에 $i$번째 증가 부분수열에 대한 정보를 출력하는데, 첫 수는 증가 부분수열의 크기 $n_i$를 출력하고, 이후에 부분수열의 원소 정보를 나타내는 $n_i$개의 수를 출력한다. 정보는 원래 수열에서의 몇 번째에 있는 원소인지를 의미한다. 정보를 출력할 때 수열의 순서를 만족해야한다.

가능한 답이 여러 가지인 경우, 그 중 아무거나 하나 출력한다.

힌트

입력 예제 1

5
3 1 2 5 3

출력 예제 1

2
2 1 4
3 2 3 5

입력 예제 2

3
3 3 3

출력 예제 2

3
1 2
1 3
1 1