Longest Increasing Subsequence

You are given several test cases. For each test case, you are given a sequence of integers that represent sales records. Your task is to determine the length of the longest strictly increasing subsequence in each sequence.

You are required to implement an efficient algorithm with a time complexity of \(O(n \log n)\). One standard approach is to use dynamic programming along with binary search. Let \(dp\) be an array where \(dp[i]\) represents the smallest possible tail value of an increasing subsequence of length \(i+1\). For each number in the sequence, perform a binary search on \(dp\) to identify the position where the number can be placed (or replaced) so that \(dp\) remains sorted. The length of \(dp\) at the end is the length of the longest increasing subsequence.

inputFormat

The first line of input contains an integer \(T\) which denotes the number of test cases. Each test case is described as follows:

• The first line contains an integer \(N\), the number of elements in the sequence.
• The second line contains \(N\) space-separated integers representing the sequence.

outputFormat

For each test case, output a single line containing the length of the longest strictly increasing subsequence.

## sample

2
6
10 22 9 33 21 50
5
3 10 2 1 20

4
3

</p>