배열 정렬

우리는 1부터 N까지의 모든 정수로 이루어진 배열 A를 정렬하기 위해 다소 난해한 정렬 알고리즘을 만드는 중이다. A의 정수들은 임의의 순서로 놓여 있을 수 있다. 입력 순서 외에도, 이 알고리즘은 두 정수 P(최대 3이다)와 K에 따라 달라진다. 알고리즘은 다음과 같이 작동한다:

• A를 서로 겹치지 않는 K개의 비어 있지 않은 부분 배열 $A_{1}$, $A_{2}$, ..., $A_{K}$로 분할하되, 이를 순서대로 이어 붙인 $A_{1}$ $A_{2}$ ... $A_{K}$이 A가 되도록, 되도록 한다.

• 각 부분 배열을 개별적으로 정렬한다.

• 부분 배열 중 최대 P개를 선택하고, 그중 임의의 두 부분 배열을 횟수 제한 없이 서로 바꾼다.

예를 들어, $A = [1 5 4 3 2]$이고 P = 2인 경우를 생각해 보자. 서로 겹치지 않는 K = 4개의 부분 배열로 가능한 한 가지 분할은 다음과 같다:

A_{1} = [1]
A_{2} = [5]
A_{3} = [4]
A_{4} = [3 2]

After Sorting Each Subarray:

A_{1} = [1]
A_{2} = [5]
A_{3} = [4]
A_{4} = [2 3]

After swapping A_{4} and A_{2}:

A_{1} = [1]
A_{2} = [2 3]
A_{3} = [4]
A_{4} = [5]

고정된 입력과 P의 값에 대해, 분할과 교환을 현명하게 선택하여 원래 순서를 정렬된 상태로 만들 수 있는 부분 배열 수 K의 최댓값을 구함으로써 이 알고리즘이 분산 환경에 적합함을 보이고자 한다. 그 K를 계산하는 것을 도와줄 수 있는가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 40초. 메모리 제한: 1GB. 1 ≤ N ≤ 5000. 모든 i에 대해 1 ≤ $X_{i}$ ≤ N. 모든 i ≠ j에 대해 $X_{i}$ ≠ $X_{j}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

P = 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

P = 3.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 구성된다. 첫 번째 줄에는 위에서 설명한 두 정수 N과 P가 주어진다. 테스트 케이스의 두 번째 줄에는 배열 A를 나타내는 N개의 정수 $X_{1}$, $X_{2}$, ..., $X_{N}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 매개변수 K로 가능한 최댓값이다.

케이스 #1: 문제 설명에서 살펴본 과정과 같다.

케이스 #2: $[4 5]$ $[1 2 3]$ 2개의 블록을 서로 바꾼다: $[1 2 3]$ $[4 5]$

케이스 #3: $[6]$ $[3 5 2 4]$ $[1]$ $[3 5 2 4]$을 정렬한 다음 $[6]$과 $[1]$을 서로 바꾸면 다음을 얻는다: $[1]$ $[2 3 4 5]$ $[6]$

케이스 #4: $[4 5]$ $[1]$ $[2 3]$ $[4 5]$과 $[1]$을 서로 바꾼 다음, $[2 3]$과 $[4 5]$을 서로 바꾼다: $[1]$ $[2 3]$ $[4 5]$

케이스 #5: $[1]$ $[2]$ $[6]$ $[4]$ $[5]$ $[3]$ $[6]$과 $[3]$을 서로 바꾼다: $[1]$ $[2]$ $[3]$ $[4]$ $[5]$ $[6]$

참고: 처음 3개의 예제 케이스는 큰 데이터 세트에 나타나지 않으며, 마지막 2개의 예제 케이스는 작은 데이터 세트에 나타나지 않는다.