MAXSET - MAXSET

Ram and Sharav are good programmers. Ram is teaching Sharav bubble sort. Whenever Ram swaps two elements in the array (while sorting), he ties a rope between the element which are swapped.

Find the size of the maximal set in the array in which none of the elements are connected with any other element after the bubble sort is done.

eg: { 1, 3, 2 }

1st iteration of bubble sort:

2 and 3 swapped so tie 2 with 3

{1, 2, 3}

2nd iteration

{1, 2, 3}
no swaps in this iteration so don't tie any element with any other element.

3rd iteration

{1, 2, 3}
no swaps in this iteration so don't tie any element with any other element.

after the end of bubble sort only 2 and 3 are tied together, so the answer for this example is 2 because the size of the maximal set in which none of the elements is not tied with any other element.

the possible maximal sets are {1, 2} (since 1 and 2 are not tied with a rope) and {1, 3} (since 1 and 3 are not tied with the rope.)

Possible subsets for this array are {1}, {2}, {3}, {1, 2}, {1, 3}, {3, 2} {1, 3, 2}, { }

out of these valid subsets are {1}, {2}, {3}, {1, 2}, {1, 3} In this valid subsets {1, 2} and {1, 3} are larger subsets. The size of both the subsets are 2, so the answer is 2.

Input

First line of input contains T - number of test cases.

First line of each test case contains n (1 <= n <= 100000) - number of elements in the array.

Second line of each test case contains n elements of the array.

output

Print the size of the maximal set (for each test case print a new line.)

Example

(from the example explained above)

Input
1
3
1 3 2

Output:
2

Note: ropes are tied between two elements which are swapped while executing the sort routine. (Bubble sort). We need the size of the set containing the maximum number of elements which are not connected to any other element in the set.


Added by:B.R.ARVIND
Date:2013-09-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2016-08-29 17:58:21
Hint: LIS
2016-01-14 20:01:56 ayush sinha
remember elements are not repeated in a set ie the key only

2013-09-19 21:02:33 Swarna
so,what should be the o/p for the test case
7
1 1 2 2 2 3 3

wont it be 7??
2013-09-16 01:22:58 Jacob Plachta
I don't know what kind of bubblesort swaps adjacent elements when they're equal, but apparently this one does?! Please clarify this in the problem statement!

For example, the answer to the case

2
1 1

is 1, rather than 2, as the two elements are swapped and so tied together.

Last edit: 2013-09-16 01:28:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.