[Solution] Positive array solution codechef

Positive array solution codechef – A 1-indexed array is called positive if every element of the array is greater than or equal to the index on which it lies. Formally, an array BB of size MM is called positive if BiiBi≥i for each 1iM1≤i≤M.

[Solution] Positive array solution codechef

For example, the arrays [1],[2,2],[3,2,4,4][1],[2,2],[3,2,4,4] are positive while the arrays [2,1],[3,1,2][2,1],[3,1,2] are not positive.

You are given an array AA containing NN integers. You want to distribute all elements of the array into some positive arrays. The elements of a positive array might not occur in the order they appear in the array AA.

Find the minimum number of positive arrays that the elements of the array AA can be divided into.

Please see the sample cases below for more clarity.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer NN — the number of elements in the array AA.
• The next line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN — the elements of array AA.

Output Format

For each test case, output on a new line the minimum number of positive arrays that the elements of the array AA can be divided into.​

[Solution] Positive array solution codechef

• 1T1041≤T≤104
• 1N1051≤N≤105
• 1AiN1≤Ai≤N
• The sum of NN over all test cases won’t exceed 21052⋅105.

Sample Input 1

5
3
2 3 3
4
3 1 1 2
3
1 1 1
5
1 2 2 4 5
6
3 2 1 2 2 1


Sample Output 1

1
2
3
2
3


[Solution] Positive array solution codechef Explanation

Test case 11: The given array is already positive. So the optimal division is [2,3,3][2,3,3].

Test case 22: One possible division is [1,2],[1,3][1,2],[1,3].

Test case 33: The only possible division is [1],[1],[1][1],[1],[1].

Test case 44: One possible division is [1,2,5],[2,4][1,2,5],[2,4].

Test case 55: One possible division is [1,2,3],[1],[2,2][1,2,3],[1],[2,2].