길이 인 수열 이 주어진다.
인덱스 을 골라 만든 수열 가 를 만족하면, 이 수열을 의 이라고 한다. 이 수열의 길이는 이다.
의 증가하는 부분수열 중 길이가 가장 긴 것들을 생각하자. 그중 원소의 합이 가장 큰 것을 의 뚱뚱한 수열이라고 한다.
의 뚱뚱한 수열과 그 원소의 합을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
case case
각 테스트 케이스마다 다음 두 줄을 출력한다.
첫째 줄에 의 뚱뚱한 수열의 원소를 앞에서부터 차례대로 공백으로 구분하여 출력한다.
둘째 줄에 의 뚱뚱한 수열의 원소의 합을 출력한다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
첫 번째 케이스에서 가장 긴 증가하는 부분수열은 하나뿐이다.
두 번째 케이스에서 가장 긴 증가하는 부분수열의 길이는 이며, 와 가 있다. 원소의 합은 각각 과 이다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 17 | (). |
| 4 | 53 | 추가적인 제약이 없다. |
세 번째 케이스에서 같은 값은 증가하는 부분수열에 함께 들어갈 수 없으므로, 가장 긴 증가하는 부분수열의 길이는 이다.
