LIS or Reverse LIS? solution codeforces

 

LIS or Reverse LIS? solution codeforces

You are given an array aa of nn positive integers.

Let LIS(a)LIS(a) denote the length of longest strictly increasing subsequence of aa. For example,

  • LIS([2,1,1,3])LIS([2,1_,1,3_]) = 22.
  • LIS([3,5,10–––,20–––])LIS([3_,5_,10_,20_]) = 44.
  • LIS([3,1,2,4])LIS([3,1_,2_,4_]) = 33.

We define array aa′ as the array obtained after reversing the array aa i.e. a=[an,an1,,a1]a′=[an,an−1,…,a1].

The beauty of array aa is defined as min(LIS(a),LIS(a))min(LIS(a),LIS(a′)).

Your task is to determine the maximum possible beauty of the array aa if you can rearrange the array aa arbitrarily.

Input

LIS or Reverse LIS? solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t104)(1≤t≤104)  — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (1n2105)(1≤n≤2⋅105)  — the length of array aa.

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (1ai109)(1≤ai≤109)  — the elements of the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 21052⋅105.

Output

For each test case, output a single integer  — the maximum possible beauty of aa after rearranging its elements arbitrarily.

Example

input

Copy

LIS or Reverse LIS? solution codeforces

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

output

  • Contestants ranked 1st will win a Apple HomePod mini
  • Contestants ranked 2nd will win a Logitech G903 LIGHTSPEED Gaming Mouse
  • Contestants ranked 3rd ~ 5th will win a LeetCode Backpack
  • Contestants ranked 6th ~ 10th will win a LeetCode water bottle
  • Contestants ranked 11th ~ 20th will win a LeetCode Big O Notebook
Copy
1
3
2

Note

LIS or Reverse LIS? solution codeforces

In the first test case, aa = [6,6,6][6,6,6] and aa′ = [6,6,6][6,6,6]LIS(a)=LIS(a)LIS(a)=LIS(a′) = 11. Hence the beauty is min(1,1)=1min(1,1)=1.

In the second test case, aa can be rearranged to [2,5,4,5,4,2][2,5,4,5,4,2]. Then aa′ = [2,4,5,4,5,2][2,4,5,4,5,2]LIS(a)=LIS(a)=3LIS(a)=LIS(a′)=3. Hence the beauty is 33 and it can be shown that this is the maximum possible beauty.

In the third test case, aa can be rearranged to [1,2,3,2][1,2,3,2]. Then aa′ = [2,3,2,1][2,3,2,1]LIS(a)=3LIS(a)=3LIS(a)=2LIS(a′)=2. Hence the beauty is min(3,2)=2min(3,2)=2 and it can be shown that 22 is the maximum possible beauty.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.