Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~n(1<=n<=3000).But there is a big problem for him.He wants soldiers sorted in increasing order.He find a way to sort,but there three rules to obey.

1.He can divides soldiers into K disjoint non-empty subarrays.

2.He can sort a subarray many times untill a subarray is sorted in increasing order.

3.He can choose just two subarrays and change thier positions between themselves.

Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5].

But he wants to know for a fixed permutation ,what is the the maximum number of K?

Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.

1.He can divides soldiers into K disjoint non-empty subarrays.

2.He can sort a subarray many times untill a subarray is sorted in increasing order.

3.He can choose just two subarrays and change thier positions between themselves.

Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5].

But he wants to know for a fixed permutation ,what is the the maximum number of K?

Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.

First line is the number of cases.

For every case:

Next line is n.

Next line is the number for the n soildiers.

For every case:

Next line is n.

Next line is the number for the n soildiers.

提交代码